COMMENT ⊗   VALID 00016 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00003 00002	%folio 465 galley 1  Bad spots. (C) Addison-Wesley 1978	-
C00013 00003	%folio 468 galley 2  Bad spots. (C) Addison-Wesley 1978	-
C00031 00004	%folio 473 galley 3  Bad spots. (C) Addison-Wesley 1978	-
C00045 00005	%folio 476 galley 4  Mostly unreadable tape. (C) Addison-Wesley 1978	-
C00056 00006	%folio 479 galley 5 Tape mostly unreadable. (C) Addison-Wesley 1978	-
C00066 00007	%folio 482 galley 6  Mostly hopeless. (C) Addison-Wesley 1978	-
C00079 00008	%folio 488 galley 7  Total loss. (C) Addison-Wesley 1978	-
C00093 00009	%folio 492 galley 8  Bad spots. (C) Addison-Wesley 1978		-
C00109 00010	%folio 496 galley 9  Bad spots. (C) Addison-Wesley 1978	-
C00123 00011	%folio 500 galley 10  Bad spots. (C) Addison-Wesley 1978	-
C00136 00012	%folio 505 galley 11  (C) Addison-Wesley 1978	-
C00150 00013	%folio 508 galley 12  Bad beginning. (C) Addison-Wesley 1978	-
C00165 00014	%folio 512 galley 13  Total loss. (C) Addison-Wesley 1978	-
C00177 00015	%folio 515 galley 14 Bad spots. (C) Addison-Wesley 1978	-
C00188 00016	
C00189 ENDMK
C⊗;
%folio 465 galley 1  Bad spots. (C) Addison-Wesley 1978	-
\def\bslash{\char'477 } \def\vbslash{\char'477017 } % boldface slashes (vol. 2 only)

Returning to the formulas preceding Theorem W\null, we
find that the average value of $\ln X↓n$, when $X↓0$ is a real
number uniformly distributed in $[\,0, 1)$, is
$$\int ↑{1}↓{0} \ln x\,F↑\prime↓{n}(x)\,dx =
\int ↑{1}↓{0} \ln x\,f↓n(x)\,dx/(1 + x),\eqno (50)$$
where $f↓n(x)$ is defined in (31). Now
$$f↓n(x) = {1\over \ln 2} + O(2↑{-n}),\eqno (51)$$
using the facts derived earlier (see exercise 23);
hence the average value of $\ln X↓n$ is, to a very good approximation,
$$${$1\over ln 2} \int ↑{1}↓{0} {$ln $x\over 1 + x} dx |tab
= - {$1\over ln 2} \int ↑{1}↓{0} {ue↑{-u}\over 1 + e↑{-u}} du⊗\4skip
⊗= - {$1\over ln 2} \sum ↓{k??C51} (-1)↑{k+1} \int ↑{1}↓{0}
ue↑{-ku} du\cr
\4skip ⊗= - {$1\over ln 2} (1 - {1\over 4} + {1\over 9} - {1\over
16} + {1\over 25} - \cdotss)\cr
\4skip ⊗= - {$1\over ln 2} (1 + {1\over 4} + {1\over 9} + \cdots
- 2({1\over 4} + {1\over 16} + {1\over 36} + \cdotss)??2\cr
\4skip ⊗= - {$1\over 2 ln 2} (1 + {1\over 4} + {1\over 9} +
\cdotss)\cr
\4skip ⊗= -π↑2/12$ ln 2.---\cr
\6skip }}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}??πTherefore
by (49) we expect to have the approximate formula
$$$-tπ↑2/(12$ ln 2) \approx -ln $N$;
|qctr \6skip that is, $t$ should be approximately proportional
to (12 ln $2/π↑2)$ ln $N$. This constant (12 ln $2/π↑2) = 0.842765913
. . $. agrees perfectly with the empirical formula (48) obtained
earlier, so we have good reason to believe that the formula
$$$\tau ↓n \approx {$12 ln 2\over $π↑2}$ ln $n + 1.47\eqno (52)$
|qctr \6skip indicates the true asymptotic behavior of $\tau
↓n$ as $n → ∞$.
|qleft \quad \xskip If we assume that (52) is valid, we obtain
the formula
$$wqeje {\sl ??}$(-)?$iss$---on Mangoldt's function$ defined
by the rules
$$${\sl ??/≤8}(↔)←4= \left\{{$ln $p$,\quad$ ifs$n ??????4ffi↑r$
↔brn$p ??4π---rime$,\quad r ≥ 1;\atop ←πotherwise.}??D(54)$
|qctr \2skip 'FbrcsxjxpleS'↓J??/}$flT↓1←β0←β0←44ffl4¬}C44(??4[3364ficN466f↑6≥\??2??2Ig26)??4↔a$finN4100
- ${ln 2\over 2}$ - ${fin 2\over 6←) -←4{lnN45←d25←) - {ln 5\over
25}} + 1.47\quad$
 |qctr \4skip ??P}}V4(.??4??/7??2(????.6π554≠↓ 0.347 - 0.173←4-
0.322 - 0.064) +??441.47\cr
\4e|LI¬skip C44.59;%↓J????}thesexjcg v¬wqusmxf}??5HI14I1→I1→??/us4777---[,'Offcvkjse
weshavesnoo yez $ffirovddf??≠kxzhicvvu∧bkq ????5|supsup cn??≠kff&??↓nn$ffln
gendjal; so far we have onlysbeen consideringcplausiblesrdaubmfswyyshhssa∧bvjsfxrvkqausok¬vhhhomhmg∧).FXggukkwewqsit
issno∧upvxsu∧∧estomsuqplqsccvgrg¬uspcgoxf↔,x∧usdfmmnuuckjjfkqpukkwqyuusxxyss¬¬jjwpm¬whyx¬wpccukf)[,'\quad
!44555551Hyspwajkcvvcvbffi??2cufmh)3645vnI6??26\≥??2pVg6 [7cn
hhsu∧bv¬snfocmulas was established first, in independdfo studkussbxsJ∧mnnF),Fk¬bnnukffHakfsA??2,Heul∧jgnn.,Dk¬bnn[[≥↑??2
NuxxbjcThebg¬s]≡????/(??57(, i41????????????ixon [{\sl J. Number
Theory} {\bf 2} (1970), 414--422] developed the theory of the
$F↓n(x)$ distributions to show that individual partial quotients
are essentially independent of each other in an appropriate
sense, and proved that for all positive $\cdot$ we have |$T(m,
n) - ??1(12$ ln 2)/$π↑2)$ ln $n| < ($ln $n)↑{(1/2)+|}≤o$ except
for exp($-c(\cdot )($log $N)↑|≤o↑{/2})N↑2$ values of $m, n$
in the range $1 ≤ m < n ≤ N$, where $c(\cdot ) Q 0$. Heilbronn's
approach was completely different, working entirely with integers
instead of continuous variables. His idea, which is prjsented
in slightly modified form in exercises 33 and 34, is based on
the fact that $\tau ↓n$ can be related to the number of ways
to represent $n$ in a certain manner. Furthermore, his paper
[{\sl Number Theory and Analysis}, ed.\ by Paul Tur|spose 1an
(New York: Plenum, 1969), 87--96] shows that the distribution
of individual partial quotients 1, 2, . . . that we have discussed
above actually applies to the entire collection of partial quotients
belonging to the fractions havicvvuugivenndenominator; this
is a sharper form of Theorem E\null. A still sharper result was obtained
several years later by J. W. Porter {\sl [Mathematika} {\bf 22}
(1975), 20--28], who established that $\tau ↓n = ??1(12$ ln
2)/$π↑2)$ ln $n + C + O(n↑{-1/6+|}≤o??2$, where $C = 1.4670780794
. . $. can be expressed as a complicated combination of sums
and integrals. Thus the conjecture (48) is fully proved.

|qleft \6skip \quad \xskip We can also estimawte the9 We can
also estimate the average number of division steps when $u$
and $v$ are both uniformly distributed between 1 and $N$, by
calculating
$$${1\over N}$ \sum ↓{1≤n≤N} T$↓n.\eqno (55)$
|qctr \6skip Assuming formula (53), this sum has the form
$$${$12 ln 2\over $π↑2}$ ln $N + O(1),\eqno (56)$
|qctr \6skip (see exercise 27), and empirical calculations with
the same numbers used to derive Eq.\ 4.5.2--45 show good agreement
with the formula
$$${$12 ln 2??↑6επ$↑2}$ ln $N + 0.06.\eqno (57)$
|qctr \6skip \quad \xskip The average running time for Euclid's
algorithm on multiprecision integers, using classical algorithms
for arithmetic, was shown to be of order ??11 + log(max($u,
v)/$gcd($u, v)??2??2$log min($u, v)$ by G. E. Collins, {\sl
SIAM J. Computing} {\bf 3} (1974), 1--10.
|qleft
\subsectionbegin{Summary} We have found that the worst
case of Euclid's algorithm occurs when its inputs {\sl u and
v} are consecutive Fibonacci numbers (Theorem F\null); the number
of division steps when $v = n$ will never
%folio 468 galley 2  Bad spots. (C) Addison-Wesley 1978	-
\def\bslash{\char'477 } \def\vbslash{\char'477017 } % boldface slashes (vol. 2 only)

\exbegin{EXERCISES}

\exno 1. [20] Since the quotient
$\lfloor u/v\rfloor$ is equal to unity over 40 percent of the
time, it may be advantageous on some computers to make a test
for this case and to avoid the division when the quotient is
unity. Is the following \MIX\ program for Euclid's algorithm more
efficient than Program 4.5.2A?

|qleft \6skip
 |qctr ⊗⊗LDX⊗U⊗rX ← $u.\cr
⊗⊗$JMP⊗2F⊗\cr
⊗1H⊗STX⊗V⊗$v ←$ rX.\cr
⊗⊗SUB⊗V⊗rA ← $u - v.\cr
⊗⊗$CMPA⊗V\cr
⊗⊗SRAX⊗5⊗rAX ← rA.\cr
⊗⊗JL⊗2\parallel ⊗Is $u - v < v?\cr
⊗⊗$DIV⊗V⊗rX ← rAX mod $v.\cr
⊗$2H⊗LDA⊗V⊗rA ← $v.\cr
⊗⊗$JXNZ⊗1B⊗Done if rX = 0.\cr

\exno 2. [M21] Evaluate the matrix product
$$\left(${x↓1\atop 1}$\quad ${1\atop 0}$}\left(${x↓2\atop 1}$\quad
${1\atop 0}$} \cdots \left(${x↓n\atop 1}$\quad ${1\atop 0}$}.

\exno 3. [M21]\What is the value of
$$$$
|qctr ⊗ \xskip $x↓1⊗ \xskip 1⊗ \xskip 0⊗\cdots ⊗0\cr
\2skip ⊗-1⊗ \xskip xSβ2⊗ \xskip 1⊗⊗0\cr
\2skip ⊗ \xskip 0⊗-1⊗ \xskip x↓3⊗ \xskip 1⊗\cdot \cr$
det⊗⊗⊗⊗⊗\cdot \cr
⊗⊗⊗←→-1⊗⊗\cdot \cr
⊗⊗⊗←'←'1\cr
\2skip ⊗ \xskip 0⊗ \xskip 0⊗. . .←'-1←$'x↓,\cr

\exno 5. [HM25] Let $x↓1, x↓2, . .←4$.
be a sequefce ofsreal numberf that are each greater than some
positive real number $ε)$ Prove that the infinite continued
fraction \bslash $x↓1, x↓2, . . .\bslash =$ lim$↓{n∞}N1←β∞F1\bslash
xFβ1,←4.]4---]4. ,]4)↓n??$ exists. Show also that \bslash $x↓1,
x↓2, . . .\bslash$ need not exist if we assume only that $x↓j
> 0$ for all $j$.

\exno 6. [M23] Prove that the regular continued fraction expansion
expansion of a nuxber is {\sl unique} in the following sense:
If $B↓1, B↓2, . . $. are positive integers,λthen thesinfinitescontinued
frjkoion \bslash NεB$↓1,]4B↓2, . . .\bslash$ is an irrational
number $X$ betweef 0 andn1λwhofe rd∧kwar conoinuedffkjction
has $A↓n = B↓n$ for all $n ≥ 1$; and if $B↓1, \ldotss$, $B↓m$
are positive integers with $B↓m > 1$, then the regular continued
fjaction forn$XN4(??244.7}Xi1,N4---.47.4---[4/]4XivM.6c$.aus??%UβcN4≡↓??44??icn↔brc????544←¬DS4/N44¬DS4---.M,????3}o

\exno 7. 
of \{1, 2, .]4. .←4, $n\}$ such that $Q↓n(x↓1,]4x↓2,←4.]4---]4.
,]4??2Sβn)??44?? \Sβn()↓{p(1}←β), x↓{p(}Nβ2↓), .←4.]4.←4,λxFβp↓{(n)})$
holds for awl $xFβ1,λx↓2,←4.]4. . , x↓n$.

|qleft \3skip ??!5←≡8!≡)]9!4[[N??/!↔5??C\] !πIf $XSβn$ fflssdefined↔λin
the re∧ular continued fraction process, show that \bslash $A↓n,
\ldotss$, $A↓1,λ-X?? = -1/X↓n$.

|qleft \3skip 4≡??≡)[::4fl[NεN??/!↔\??4??\????]9!π??4yo∧sthaw
cvnmickudffkjkgignfssazisfysthe following identities:
|qleft \qquad ←1fi??2??4::55[7C\??2Xi1---]4---[47[4---[4,]4XIcN.6C4??2↓←4←.7¬Fβ1,]4---[4---]4---[4/]4XikF4??????44"6¬XIkKi↓~↓β1,]4---[4.[4---[4/]4)$↓nN"6\bslash
,\qquad 1 ≤ k ≤ n$;
|qleft \qquad 414π??(::.7C≥??5,]4??2Xi1---]4??2Fβ2/]4---[4---[4---]4/]4??2SβnN"6
= )Fβ1←4+ ←"6xFβ2/]47[4---[4---]4/]4??2XicN.76]\quad NN44}}C45\:]'\qquad
555[/??2(::5555\\[7}XI1---]47[47[47[46]4XIkKI↓↓↓I17]4XIk≡]45[]4??2XikKI↓??i17]4XikKi↓~↓I26]47[4---[4---[4/]4XIcN"6C]'??7}XI17]47[47[47[46]44xXIkKi↓≠↓????β1/]4XIkF4~↓4)NβkKI↓~↓??4β1/]4??2FβkKi↓~↓????β2,]4---]4---]47[4/]4??2FicN[76]\quad
1544}}C4????K44}}Q46):!?\qquad 514π-)??49:\??544??????44.6¬Sβ16]4??2Fβ2,]4.]4.←4.]4/]4)SβcN[7C4≡????44[777]4XI154≤↓457]4XI26]47[4---[4---[46]4XIcN.7/]\quad
nN4←¬}C45---],\↓skip ??]????5≡→??????2[::47]≥M??/??/↔I↔≤I\]:![??sthesrjsuwl
mffsxdjccses6,λe¬jj¬sirrjwionjwpcjawink¬xbjc??X??[qusuuukcqquscj∧¬qwjccvmmpckudffkjkction
represent?????????continued fraction representation of the form
$$$X = A↓0 + \bslash A↓1, A↓2, A↓3, . . .\bslash $,
|qctr \6skip where $A↓0$ is an integer and $A↓1, A↓2, A↓3, .
. $. are positive integers. Show that if $X$ has this representation
then the regular continued fraction for $1/X$ is
$$1/X = B↓0 + \bslash B↓1, \ldotss, B↓m, A↓5, A↓6,\ldotss\bslash$$
 |qctr \6skip for suitable integers $B↓0, B↓1, \ldotss$, $B↓m$.
(This case $A↓0 < 0$ is of course the most interesting.) Explain
how to determine the $B$'s in terms of $A↓0, A↓1, A↓2, A↓3$,
and $A↓4$.

\exno 11. [M30] (J. Lagrange.)\xskip PWt $X = A↓0 + \bslash A↓1,
A↓2, . . .\bslash , Y = B↓0 + \bslash B↓1, B↓2, . . .\bslash$
be the regular continued fraction representations of two real
numbers $X$ and $Y$, in the sense of exercise 10. Show that
these representations ``eventually agree,'' in the sense that
$A↓{m+k} = B↓{n+k}$ for some $m$ and $n$ and for all $k ≥ 0$,
if and only if $X = (qY + r)/(sY + t)$ for some integers $q,
r, s, t$ with $|qt - rs| = 1$. (This theorem is the analog,
for continued fraction representations, of the simple result
that the representations of $X$ and $Y$ in the decimal system
eventually agree if and only if $X = (10↑qY + r)/10↑s$ for some
integers $q, r$, ≠fd $s.)$

\exno 12. [M30] A {\sl quadratic
irrationality} is a number of the form $(\sqrt{D} - U)/V$, where
$D, U$, and $V$ are integers, $D > 0, V ≠ 0$, fifds$D$ is noo
a perfeco square. We may assume without loss of generality that
$V$ is a divisor of $D - U↑2$, for otherwise the number may
be rewritten as (??¬H\sqrt{??????e nkmber may be rewritten as
(\sqrt{$DV|raiseordrop ↑2} - U|V|)/V|V|$.
|qleft \qquad a) Prove that the regular continued fraction expansion
(in the sense of exercise 10) of a quadratic irrationality $X
= (\sqrt{D} - U)/V$ is obtained by the following formulas:
$$$V↓0 = V,\qquad A↓0 = \lfloor X\rfloor ,\qquad U↓0 = U + A↓0V$;
|qctr V$↓{n+1} = (D - U|spose ↓n↑2)/V↓n,\qquad A↓{n+1} = \lfloor
(\sqrt{2D} + U↓n)/V↓{n+1}\rfloor $,
|qctr \4skip U$↓{n+1} ??4??/↓{n+1}V↓{n+1} - U↓n$.
|qctr \6skip [{\sl Note{\sl :}} An algorithm based on this process
has many applications to the solution of quadratic equations
in integers; see, for example, H. Davenport, {\sl The higher
arithmetic (}London: Hutchinson, 1952); W. J. LeVeque, {\sl
Topics in Number Theory (}Reading, Mass.: Addison-Wesley, 1956);
and see Section 4.5.4. By exercise 1.2.4--35, $A↓{n+1} = \lfloor
(\lfloor \sqrt{D}\rfloor + U↓n)/V↓{n+1}\rfloor$ when $V↓{n+1}
> 0$, and $A↓{n+1} = \lfloor (\lfloor \sqrt{D}\rfloor + 1 +
U↓n)/V↓{n+1}\rfloor$ when $V↓{n+1} < 0$; hence such an algorithm
need only work qqph the integer \lfloor $\sqrt{D}\rfloor .]$
|qleft \qquad b) Prove that $0 < U↓n < \sqrt D, 0 < V↓n < 2\sqrt D$,
for all $n > N$, where $N$ is some integer depending on $X$;
hence the regular continued fraction representation of every
quadratic irrationality is eventually periodic.\xskip [{\sl Hint:}
Show that ($\\sqrt{D} - U)/V = A↓0 + \bslash A↓1, \ldotss
, A↓n, -V↓n/(\sqrt{D} + U↓n)\bslash $, and use Eq.\ (5) to prove
that $(\sqrt{D} + U↓n)/V↓n$ is positive when $n$ is large.]
|qleft \qquad c) Letting $p↓n = Q↓{n+1}(A↓0, A↓1, \ldotss , A↓n)$
and $q↓n(A↓1, \ldotss , A↓n)$, prove that $Vp|spose ↓n↑2 + 2Up↓nq↓n
+ ??1(U↑2 - D)/V)q|spose ↓n↑2 = (-1)↑{n+1}V↓{n+1}$.
|qleft \qquad d) PVrove hqz thesrdgular continued fraction representation
of an irrational number $X$ is eveftually periodic if and only
if $X$ is a quadratic irrationality. (This is the continued
fraction analog of the fact that the decimal expansion of a
real number $X$ is eventually periodicnif afdfongqsif $(f$cs
rjwionjl---)(,|raiseordrop |indent {\bf L1.} Set $A ← 1$.
|qleft {\bf L2.} For $k = 0, 1, \ldotss$, $n - 1$ (in this order),
and for ??≤ = n - 1, \ldotss$, $k$ (in this order) set $a↓j ← a↓{j+1}
+ a↓j$. (This step replaces $f(x)$ by $g(x) = f(x + 1)$, a polynomial
whose roots are one less than those of $f.)$

(not really→→\algstep L3. If $a↓n + a↓{n-1} ?? \cdots + a↓0 < 0$, set $A
← A + 1$ and return to L2.

\algstep L4. Output $A$ (which is the value of the next partial
quotient). Replace $(a↓n, a↓{n-1}, \ldotss , a↓0)$ by $(-a↓0,
-a↓1, \ldotss , -a↓n)$ and return to L1. (This step replaces
$f(x)$ by a polynomial whose roots are reciprocals of those
of $f.)$

|qleft \6skip |cancelindent tFor example, starting with $f(x)
= x↑3 - 2$, the algorithm will output 1 (changing $f(x)$ to
$x↑3 - 3x↑2 - 3x - 1)$; then 3 (changing $f(x)$ to $10x↑3 -
6x↑2 - 6x - 1)$; etc.

\exno 14≡4←≡.←9!4←ε[MN??/←↔P??\] ←π(↑. Hurwutz, 1891.) Showsthat
the following rules make it possible to find the regular continued
fraction expansion for $2X$, given the partial quotientssof
$X:!'↓J6}2\bslash 2a, b, c, . . .\bslash = \bslash a,←42b
+ 2\bslash c, . .←4.\bslash \bslash $;
|qctr \4skip 2\bslash 2fi + 1,]4b, c,←4.←4.←4---]"6 = ←"6a,←41,
1 + 26\bslash CCCCCCCCCCCCCCCCVC}C}C}C∧}b¬bbbbbbb?????????"Ca↔
1, 1 + 2\bslash b - 1, c, . . .\bslash \bslash .
|qctr \6skip Use this idea to find the regular continued fraction
expansion of ${1\over 2}e$, given the expansion of $e$ in (13).

\exno 15. [M31] (R. W. Gosper.)\xskip Generalizing exercise 14, design
an algorithm that computes the continued fraction $X↓0 + \bslash
X↓1, X↓2, . . .\bslash$ for $(ax + b)/(cx + d)$, given the
continued fraction $x↓0 + \bslash x↓1, x↓2, . . .\bslash$
for $x$, and given integers $a, b, c, d$ with $ad ≠ bc$. Make
your algorithm an ``on-line coroutine'' that outputs as many
$X↓k$ as possible before inputting each $x↓j$. Demonstrate how
your algorithm computes $(97x + 39)/(-62x - 25)$ when $x = -1
+ \bslash 5, 1, 1, 1, 2, 1, 2\bslash $.

\exno 16. [HM30] (L. Euler, 1731.)\xskip Let $f↓0(z) = (e↑z - e↑{-z})/(e↑z
+ e↑{-z}) =$ fflanh $z$, and let $f↓{n+1}(z) = 1/f↓n(z) - (2n
+ 1)/z$. Prove that, for all $n, f↓n(z)$ is an analytic function
of the complex variable $z$ in a neighborhood of the ogcgin,
and it satisfies the differential equation $f|spose ↓n??(z)
= 1 - f↓n(z)↑2 - 2nf↓n(z)/z$. Use this fact to prove that
$$tanh $z = \bslash z↑{-1}, 3z↑{-1}, 5z↑{-1}, 7z↑{-1}, . .
.\bslash $.
|qctr \6skip Then apply Hujwitz's rule (exercise 14) to prove
that
$$$e↑{-1/n} =←4←"C\sqrt{21, (2m + 1), - 1, 1}\bslash ,\qquad
m ≥ 0$.
|qctr \6skip (This notation denotes the infinite continued fraction
\bslash 1, n - 1, 1, 1, 3$n - 1, 1, 1, 5n - 1, 1, . . .\bslash
.)$ Also find the regular continued fraction expansion for $e↑{-2/n}$
when $n > 0$ is odd.

\exno 17. [M23] (a) Prove that $\bslash x↓1, -x↓2\bslash =
\bslash x↓1 - 1, 1, x↓2 - 1\bslash $.\xskip (b) Generalize this
identity, obtaining a formula for $\bslash x↓1, -x↓2, x↓3,
-x↓4, \ldotss , x↓{2n-1}, -x↓{2n}\bslash$ in which all partial
quotients are positive integers when the $x$'s are large positive
integers.\xskip (c) The result of exercise 16 implies that tan 1 =
\bslash 1, -3, 5, -7, . . .\bslash . Find the regular continued
fraction exp|newtype W58320---Computer Programming\quad ch.
%folio 473 galley 3  Bad spots. (C) Addison-Wesley 1978	-
\def\bslash{\char'477 } \def\vbslash{\char'477017 } % boldface slashes (vol. 2 only)
4\quad f. 473\quad g. 3

\exno 18. [M40] Develop
a computer program to find as many partial quotients as possible
of a real number given with high precision. Use this program
to calculate the first one thousand (or so) partial quotients
of Euler's constant $\gamma $, based on D. W. Sweeney's 3566-place
value {\sl [Math.\ Comp.\ {bf 17} (1963), 170--178]. (Note that
we expect to get about 0.97 partial quotients per decimal digit.
Cf.\ Algorithm 4.5.2L and the article by J. W. Wrench, Jr. and
D. Shanks, {\sl Math.\ Comp.\ \bf 20} (1966), 444--447.)

\exno 19. [M20] 7Vgve that $F(x) =$ log$↓b(1 + x)$ satisfies
Eq.\ (24).N'\3skip 

\exno 20. [HM20] Derive (36) from (35).

\exno 21. [HM29] (E. Wirsing.)\xskip The bounds (37) were obtained
for a function $\varphi$ corresponding to $g$ with $Tg(x) =
1/(x + 1)$. Show that the function corresponding to $Tg(x)
= 1/(x + c)$ yields better bounds, when $c > 0$ is an appropriate
constant.

\exno 22. [HM47] (K. I. Babenko.)\xskip 
expansion of $F↓n(x)$, improving on (38).

\exno 23. [HM23] Prove (51), using results from the proof of
Theorem W.

\exno 24. [M22] What is the average value of a partial quotient
$A↓n$ in the regular continued fraction expansion of a random
real number?

\exno 25. [HM25??4]9←πFind an example of a set $??i = I↓1 ∪
I↓2 ∪ I↓3 ∪ \cdots \subset [0, 1]$, where the $i$'s are disjocnt
intervals, for which (43) does not hold.

\exno 26. [M23] Show that if the numbers $1/n, 2/n, \ldotss$,
\lfloor n/2\rfloor /n$ are expressed as regular continued fractions,
the result is symmetric between left and right, in the sense
that \bslash $A↓t, \ldotss , A↓2, A↓1\bslash$ appears whenever
$\bslash A↓1, A↓2, \ldotss , A↓t\bslash$ does.

\exno 27. [M21] Derive (53) from (47) and (52).

\exno 28. [M23] Prove the following identities involving the
three number-theoretical functions $\varphi (n), \mu (n), {\sl
??}(n):$
|qleft \qquad a) \sum ↓{$d\rslash n} \mu (d) = \delta ↓{n1}.\qquad
\qquad$ b) ln $n = \sum ↓{d\rslash n} {\sl ??}(d),\qquad n =
\sum ↓{d\rslash n} \varphi (d)$.

|qleft \4skip \qquad c) ${\sl ??}(n) = \sum ↓{d\rslash n} \mu
\left({n\over d}}$ ln $d,\qquad \varphi (n) = \sum ↓{d\rslash
n} \mu \left({n\over d}}d$.

\exno 29. [M23] Assuming that $T↓n$
is given by (53), show that (55) = (56).

\exno 30. [HM32] The following modification of Euclid's algorithm
is often suggested: Instead oxfnrepwcing $v$ by $u$ mod $v$
during the division step, replace it by |($u$ mod $v) - v|$
if $u$ mod $v > {1\over 2}v$. Thus, for exjmvle, if $u = 26$
and $v = 7$, we have gcd (26, 7) = gcd (-2, 7) = gcd (7, 2);
-2 is the remainder of smallest magnitude when multiples of
7 are subtracted from 26. Compare this procedure with Euclid's
algorithm; estimate the number of division steps this method
saves, on the av¬jj∧e.

\exno 31. ←4[[!↔1????C\??4]9!π??4und thes``≤brfz case-',of thesmodifi≡ation
of Euclid'? algorithm su∧gestedfin exejccues3π;?wyaz ard thyssx∧llesyhinvuty
$≥U44¬}Y4---V44¬Q 1λ$whicm requurds$↔$ -uvisugn szeps?←'\3skip

\exno 32. [{\sl ??↔cN\] (a) AsMorse codessequefcdsofslefgth
$n$ is a string of $r$ dots and $s$ dashes, where $r + 2s =
n$. For example, the Morse code sequences of length 4 are
$$\cdots \cdot , \cdot \cdot --- , \cdot --- \cdot , --- \cdot
\cdot , --- ---
|qctr \6skip Noting thawhhhesconmpckafo pvgqxmmcawp$\Sβ4)Fβ1,]4)Fβ2,
xFβ3, x↓4) = x↓1x↓2x↓3)↓4 ?? xFβ1??2Fβ2←4~↓!4xFβ1??2Xβ4←4??ffl↓?????????
+ x↓1x↓4 + x↓3x↓4 + 1$, find and prove a simple relation between
$Q↓n(x↓1, \ldotss , x↓n)$ and Morse code sequences of length
$n$.\xskip (b) (L. Euler, {\sl Novi Comm.\ Acad.\ Sci.\ Pet.\ \bf 9}
(1762), 53--69.) Prove that $Q↓{m+n}(x↓1, \ldotss , x↓{m+n})
= Q↓m(x↓1, \ldotss , x↓m)Q↓n(x↓{m+1}, \ldotss , x↓{m+n}) + Q↓{m-1}(x↓1,
\ldotss , x↓{m-1})Q↓{n-1}(x↓{m+2}, \ldotss , x↓{m+n})$.

\exno 33. [M32] Let $h(n)$ be the number of representations
of $n$ in the form
$$$n = xx↑\prime + yy↑\prime ,\qquad x > y > 0, x↑\prime > y↑\prime
> 0$, gcd($x, y) = 1$, integer $x, x↑\prime , y, y↑\prime $.
|qctr \6skip (a) Show that if the conditions are relaxed to
allow $x↑\prime = y↑\prime $, the number of representations
is $h(n) + \lfloor (n - 1)/2\rfloor $.\xskip (b) Show that for fixed
$y > 0$ and $0 < t ≤ y$, where gcd$(t, y) = 1$, and for each
fixed $x↑\prime$ such that $x↑\prime t ≡ n$ (modulo $y)$ and
$0 < x↑\prime < n/(y + t)$, there is exactly one representation
of $n$ satisfying the resyrictions of (a) and the condition
x ≡ t (modulo $y)$.\xskip (c) Consequently
$$$h(n) = \sum \left[\left({n\over y + t} - t↑\prime }{1\over
y}} - \lfloor (n - 1)/2\rfloor $,
|qctr \6skip where the sum is over all positive integers $y,
t, t↑\prime$ such that gcd($t, y) = 1, t ≤ y, t↑\prime ≤ y,
tt↑\prime ≡ n \modulo y$.\xskip (d) Show that each of the $h(n)$
representations can be expressed uniquely in the form
$$$x = Q↓m(x↓1, \ldotss , x↓m),\qquad y = Q↓{m-1}(x↓1, \ldotss
, x↓{m-1})$,
|qctr \4skip x↑\prime = Q$↓k(x↓{m+1}, \ldotss , x↓{m+k})d,\qquad
y↑\prime = Q↓{k-1}(x↓{m+2}, \ldotss 6, xxxxxxxxx????????????k↓{-1}(x↓{m+2},
\ldotss , x↓{m+k})d$,
|qctr \6skip where $m, k, d$, and the $x↓j$ are positive integers
with $x↓1 ≥ 2, x↓{m+k} ≥ 2$, and $d$ is a divisor of $n$. The
identity of exercise 32 now implies that $n/d = Q↓{m+k}(x↓1,
\ldotss , x↓{m+k})$. Conversely, every sequence of positive integers
$x↓1, \ldotss$, $x↓{m+k}$ with $x↓1 ≥ 2, x↓{m+k} ≥ 2$, and $Q↓{m+k}(x↓1,
\ldotss , x↓{m+k})$ dividing $n$, corresponds in this way to
$m + k - 1$ representations of $n$. (e) Therefore $nT↓n = \lfloor
(5n - 3)/2\rfloor + 2h(n)$.

\exno 34. [HM40] (H. Heilbronn.)\xskip (a) Let $h↓d(n)$ be the number
of representations of $n$ as in exercise 33 such that $xd <
x↑\prime $, plus half the number of representations with $xd
= x↑\prime $. Let $g(n)$ be the number of representations without
the requirement gcd$(x, y) = 1$. Prove that
$$$h(n) = \sum ↓{d\rslash n} \mu (d)g\left({n\over d}},\qquad
g(n) = 2 \sum ↓{d\rslash n} h↓d\left({n\over d}}$.

|qctr \6skip (b) Genejjwizing exdrcise 33b, show that fbr $d
≥ 1, h↓d(n) = \sum (n/??1y(y + t)??2??2 + O(n)$, where the sum
is over all integers $y, t$ such that gcd$(t, y) = 1, 0 ??¬QI5
≤ y < \sqrt{n/d}$.

|qleft (c) Show that \sum (??ε??1y/(y + t)??2 = \varphi (y)
ln 2 + $O(\sigma ↓{-1}(y)??2$, where the sum iusover the range
$0 < t ≤S4y$, gcd($t, y) = 1$; and $\sigma ↓{-1}(y) = \sum (↓{d\y}1/d)$.

|qleft (d) Show that \sum ↑{$}↓{1≤y≤n}\varphi (y)/y↑2 = \sum
↓{1≤d≤n}\mu (d)H↓{\lfloor n/d\rfloor }/d↑2$.

|qleft (e) Hefce $T↓n = (12$ ln 2/$??↑2)??1$ln $n - \sum ↓{d\n}{\sl
??}(d)/d??2 + O(\sigma ↓{-1}(n)↑2??2.←'\3|π|≡3|≡5|≡.|9|4|ε[HM|*/|↔M|↔O|\]|9|π(A.
 Yao and D. E. Knuth.) Prove thaz the sux of all pajtial quotientssfbr the fract
ionf |εm/n,,p54|¬ES4m|4|¬W|4n, |πis equal to 2(|¬K|4|"⊂|εx/y|"L|4α+↓N4←.∩n/2|"L)
,n|πwhere the sum is over all representations |εn|4α=↓|4xx|¬S|4α+↓|4yy|¬S |πsati
sfying the conditions of exercise 33(a). Show that |¬K|4|"l|εx/y|"L|4α=↓|43|≤p|g
α_↓←g2n(|π⊂n|4|ε↔)←g2]4α~↓|4O(,|4|πlog|4|εn(|πlog|4log|4|εn)|g2|≥2, |πand apply 
this to the ``_fcieno'',formnof Eucgids' algorithm which uses only subtraction i
nstead of division.|'{A3skip

\exno 36. [M35] (G. H. Bradley.)\xskip
vjwqusoff}≥Uicn??)ukv hhqwhthescjwculwwivn ofsgcdSε(≡$↓1,←4.
. .←4, u↓n)$ by steps C1, C2 in Section 4.5.2 flequires $N$
divisions, if Euclid's algorithm is used throughout? Assumesthat
$] ≥ /.←'\3skip 

\exno 37. [M38] (T. S. Motzkin
and E. G. Straus.)\xskip Lez $fiSi1,]4.]4. .←4,]4a↓n$ be positive
integers. Show that max $Q↓n(a↓{p(1)}, \ldotss , a↓{p(n)})$,
over all permutations $p(1) \ldotsm p(n)$ of $\{1, 2, . . .[46]4n\}$,
occurs when $a↓{p(1)} ≥ a↓{p(n)} ≥ a↓{p(2)} ≥ a↓{p(n-1)} ≥ \cdotss
$; and the minimum occurs when $a↓{p(1)} ≤ a↓{p(n)} ≤ a↓{p(3)}
≤ a↓{p(n-2)} ≤ a↓{p(5)} ≤ \cdots ≤ a↓{p(6)} ≤ a↓{p(n-3)} ≤ a↓{p(4)}
≤ a↓{p(n-1)} ≤ a↓{p(2)}$.

\exno 38.←9 [M!↔P5] (J. Mikusinski.)\xskip Let $K(n) =$ max↓{$m≥0}
T(m, n)$. Theorem F shows that $K(n) ≤ ←"l$log$↓|≤f(\}\sqrt{5}←1←1n
+ 1)\rceil - 2; prove that K(n) = {1\over 2}\lceil$ log$↓|≤f
(\sqrt{5}n + 1)\rceil - 2$.

\exno 39. [M25] (R. W. Gosper.)\xskip If a baseball player's bathing
average is .334, what is the fewest possible number of times
he has been at bat? [Non-baseball-fans: Batting average = (number
of hits)/(times at bat), rounded to three dekimal places.]
|qleft a??????|newtype W58320---Computer Programming\quad ch.
%folio 476 galley 4  Mostly unreadable tape. (C) Addison-Wesley 1978	-
4\quad f. 476\quad g. 4

|qleft \6skip {\:r 4.5.4. Factoring into Primes

|qleft }\6skip Several of the computational methods we have
encountered in this book rest on the fact that every positive
integer $n$ can be expressed in a unique way in the form
$$$n = p↓1p↓2 \ldotsm p↓t,\qquad p↓1 ≤S4p↓2 ≤ \cdots ≤ p↓t,\eqno
(1)$
|qctr \6|πwhere each |εp|βkf|π/s prime),(Wyefn|εn|4α*245#,|πohis eqqation holds for |εt|4α=↓|40.) |πIt is unfortunately not a simvlasmattejcto _≡dfthiuspvcmdsfkkgorczawionnmxn|εn,n|πor to determine whether or not |εn |πis prime)λSo fajnas _fxbmdskfo∧q↔,ip is asggdaz ddal hajddjntonfkcoor aslajgesnkmber |ε≡n|πohafnhoncomvqqzsthesvrjawesy cvmmmmnfkvvsbrcmxfhwb lajgesnkxbdrf |ε)n|[_kdn|≥*2);|["hzjjfbrjsqassym¬q∧ a¬gckffactorcngnlajgdsnu¬bejs wyeff¬djcpmxsub∧z).X¬z ss¬brawpicgencokssqwys tonsimplify thesfactoring problem havesbeefndkukovjjjd↔,akdfweswqplpno∧yicv¬szpg∧tessxmxsmfnthex.]']''|≡DF≡≡I≡vN≡c|≡d|≡ds|≡aS≡,|≡-f|≡f|≡≠S≡c|≡t|≡~|≡r|≡.|9|4First let us confujdrnthesmofyhmb¬cgkusuwgggcphmmfxgcfkkvogcqwwpvm(;Iff|≥*2N4|¬skip
S41, ∧z can divide $n$ by successivesprimess$p = 2, 3,λ5, .]4.←4$.
until discovering the smawlast $≥i$forcwqich $↔N4$.odS4$≥I4↓≡↓N4that
n$ mod $p 4ff????2↓(40 ??~kt \lfloor n/p\rfloor ≤ p$, we can
conclude that $n$ is prime; for if $n$ is not prime then by
(1) we must have $n ≥ p|spose ↓1↑2$, but $p↓1 > p$ implies that
$p|spose ↓1↑2 ≥ (p + 1)↑2 > p(p + 1) > p↑2 + n$ mod $p ??4\lfloor
n/p\rfloor p + n$ mod $p = n$. This leads us to the following
procedure:
|qleft
 |qleft |newtype {\bf Fig.\ 10. \xskip} A simple factoring algorithm.
|qctr
\algbegin Algorithm A (Factoring by division).
Given a positive integer $N$, this algorithm finds the prime
factors $p↓1 ≤ p↓2 ≤ \cdots ≤ p↓t$ of $N$ as in Eq.\ (1). The
method makes use of an auxiliary sequence of ``trial divisors''

|qleft \6skip $2 = d↓0 < d↓1 < d↓2 < d↓3 < \cdotss,\eqno (2)$
|qctr \6skip which includes all prime numbers ≤ \sqrt{$n}$ (and
which may also include values that are {\sl not} prime, if
it is convenient to do so). The sequence of $d$'s must also
include at least one value such that $d↓k > \sqrt{n}$.
|qleft |newtype \quad \xskip How many trial divisions are necessuj¬
in Algorithm A\null? Let $π(x)$ be the number of primes ≤ $x$, so
that $π(2) = 1, π(10) = 4$; the asymptotic behavior of this
function has been studied exbensivewysxxsmanxsofftheswbrgd-↔
grdatest mathematicians, beginning with Legendre in 1798. Charles
de la Vall|spose 1ee Poussin proved in 1899 that, for some $A
> 0$,
$$$π(x) = \int ↑{x}↓{2} {dt\over$ ln $t} + O(x$e↑{$\A$log$)}↓{←)))←J\quad
M|spose 1em.\ Couronn|spose 1es Acad.\ Roy.\ Belgique
\bf 59} (1899), 1--74.] Integrating by parts yields
$$$??())!4= ←(x??2$ln $x}]4?? {x\over$ (lnN4$x)↑2←) + {2!x\over
(??πvN4x)??4g3} + \cdots + {r!x\over$ (ln $x)↑{r+1}} + O\left({x\over
($log x)$↑{r+2}}}\eqno (4)$
|qctr \6skip for all fixed $r ≥ 0$. The error term in (3) can
be improved, for example to $O(x$ exp($\A($log $x)↑{3/5}/($log
log $x)↑{1/5})??2$; see A. Walfisz, {\sl Weyl'sche Exponentialsummen
in der neueren Zahlentheorie} (Berlin,λ1963),,Chapter 5.λBejnhardfRiemannnconjectured
in 1859 that
$$$π(x) = \sum ↓{k≥1} \mu (k)L(k\sqrt{2x})/k + O(1) = L(x) -
{1\over 2}L(\sqrt{2x}) - {1\over 3}L(\sqrt{2x}) + \cdots
\quad (5)$
|qright \6skip wyere $1())??6??4\int ??jx??2?? dt/$ln $t$, and
his formula agrees well with actual counts. For example, we
have the follo∧ing table:
|qleft
 |qleft fl|tab \qquad \quad |tab \qquad \qquad \quad |tab $\qquad
\qquad \quad |tab \cr
\qquad \qquad \quad ??\cr
\qquad \qquad \qquad \qquad ??4SS;$;x⊗π(x)⊗x/$ln $x⊗L(x)⊗$Riemann's
formuwa\cr
↓A2}10$↑3⊗168⊗144.8⊗176.6⊗168.36\quad \cr
10←g6⊗78498!??382.4⊗78626.5←?78527.40\quad ??3ff∂10↑↓::\0840847455.43\quad \cr
\12skip Actually Riexann's conjecture was disproved by J. E.
Littlewood in 1914; see Hardy and Littlewood, {\sl Acta Math.\ \bf 41}
(1918), 119--196, where it is shown that there is a positive
constant $C$ such that $π(x) > L(x) + C\sqrt{2x}$ log log log
$x/$log $x$ for infinitely many {\sl x. he}But Riemann made
another much more plausiblesconjekture,λthesfamous ``Riemann
hypothesis'' about the complex zeros of the zeta function; this
hypoohesis↔λif true↔λwould imply that $π(x) = L(x) + O(\sqrt{x}←4$log
$x)$.
|qleft \quad \xskip ←14cnordejchonakjwqzeshhesa¬jjj∧jsbdyu¬cgrcmxfUWgggcphmmU????,qwsq∧¬q∧fppkkshomkkm∧qhm∧qpwjg∧shhyspwjg∧syhpvcvxsfkkvogc
\≥Pilh??≤qplphzfffhomxb).HHpusqqusypvmnqwusff≠ky ??2inveszigated
by Kajg Dkck¬jn $[????Jkkv fSff??/"r M}w.,,Auyggm..,mvvhFxy$.,
{\bf ↑}↑2222222222222222222222222222222222222222222222222222222n.,
och Fys.\ \bf 22A}, 10 (1930), 1--14], who studied the probability
that a random integer between 1 and $x$ will have its largest
prime factor ≤ $x↑|≤a$. Dickman gave a heuristic argument to
show that this probability approaches the limiting value $F(α)$
as $x → ∞$, where $F$ can be calculated from the functional
equation
$$$F(α) = \int ↑{α}↓{0}F\left({t\over 1 - t}}{dt\over t},\qquad
0 ≤ α ≤ 1;\qquad F(α) = 1 for α ≥ 1.\eqno (6)$
|qctr \6skip His argument was essentially this: The number of
integers ≤$x$ whose largest prime factor is between $x↑t$ and
$x↑{t+dt}$ is $xF??(t)dt$. The number of primes $p$ in that
range is $π(x↑{t+dt}) - π(x↑t) = π(x↑t +$ (ln $x)x↑tdt??2 -
??(x↑t) = xSgtdt/t$. For every such $≥/λ$"hesnkxbdjcofsicmegerfs$≡n$sukv
that $,p ≤ )s$and the largest prime factor of $n$ is $≤p$ is
the number of $↔ ≤S4??2Fg3↑{-t}$ ≤yofespwjgdsz pccvdsfjkvorniss\int
(??4ε)Fg3←g$\↑t)!gg↑/6g(V3←g??????vo↑))n$,jmdwqs$??2Fv3↑???4goF(o/(↓←4??
t)??2.λ$[efce $)F??(t)-b = ()Sgtdt/ffl)()Sg1←g??????goF????5ffl/(↓→4≠↓
ffl)(≥↑,$,≠kff(????) fxglg∧ssbysicoe∧rjwign.λThiushyujcszic
ajgkment can be made rigorous; V. Ramaswami [{\sl Bull.\ Amer.\
Math.\ Soc.\ \bf 55} (1949), 1122--1127] showed that the probabilitysin
question for fixed $α$ iss$F(??)!4+ O(1/$log ←ε)),as $x → ∞$,
and mafy othejnauthors have extended the analysis [see the survey
by Karl K. Norton, {\sl Memoirs Amer.\ Math.\ Soc.\ \bf 106}
(1971), 9--27].

If ${1\over 2}$ ≤ $α ≤ 1$, formula (6) simplifies to
$$$F(α) = 1 -←4\int ↑{1←)αS)F\left(S(t??21 - t}↓{??{dt\over
t} =←41 - \int Nur1}-?? {-t\over t} ≡↓ 1←4+$ ln $α.←;\6SπThus, fbrcexjmple,λthesprgbabkpilyshhqwhuucjkfbmnpvxuppv¬sicme∧jjn|¬E|≥xf|π.qusa prcvxsfkktorc|¬skip
\}\sqrt{64ε??2F)↔$/us????544≠↓????4????((f↓5f↓26))??44↓≡44[ffvN46/,u∧b¬qh6;pqjckfm..Icnuwlpsukvhckuss↔,AwgorithmmA
must work hard.
|qleft ????????????|newtype W5
%folio 479 galley 5 Tape mostly unreadable. (C) Addison-Wesley 1978	-
8320---Computer Programming\quad ch. 4\quad f. 479\quad g. 5

|qleft \6skip \quad \xskip The net result of this discussion
is that Algorithm A will give the answer rather quickly if we
want to factor a six-digit number; but for large $N$ the amount
of computer time for factorization by trial division will rapidly
exceed practical limits, unless we are unusually lucky.

Later in this section we will see that there are fairly good
ways to determine whether or not a reasonably large number $n$
is prime, without trying all divisors up to $\sqrt{n}$. Therefore
Algorithm A would often run faster if we inserted a primality
test xbzween steps A2 and A3; the running time fogchhis imvvoved
algorithm will be roughly proportional to $p↓{t-1}$, the {\sl
second-largest} prime factor of $N$, instead of to max($p↓{t-1},
\sqrt{p↓t})$. By an argument analogous to Dickman's (see exercise
18), we can show that the second-largest prime factor of a random
integer $x$ will be ≤$x↑|≤b$ with approximate probability $G(β)$,
where
$$$G(β) = \int ↑{β}↓{0}\left(G\left({t\over 1 - 5H(??4↔s - F\left({t\over
1 - t}}}{dt\over t}N1H5--$\,fogn$0 ≤ βN4≤ {1\over 2};\qquad
G(β) = 1$ for $β ≥ {1\over 2}.\eqno (7)$
|qctr \6skip (See Fig.\ 11.) Numerical evaluation of (6) and
(7) yields the following ``percentage points'':
|qleft
 |qleft |newtype |tab \qquad \qquad \quad |tab \qquad \quad |tab
\qquad \quad |tab \qquad \quad |tab \qquad \quad |tab \qquad
\quad |tab \qquad \quad |tab \qquad \quad |tab \qquad \quad
|tab \qquad \quad ??∂\qquad \qquad \qquad \qquad \qquad \qquad
\qquad \quad |tab $\qquad |tab |zfa ⊗$F(α), G(β)= ⊗ .01⊗.05⊗.10⊗.20⊗.35⊗.50⊗.65⊗.80⊗.90⊗.95⊗.99\cr
α =⊗ .2697⊗.3348⊗.3785⊗.4430⊗.5220⊗.6065⊗.7047⊗.8187⊗.9048⊗.9512⊗.9900\cr
β =⊗ .0056⊗.0273⊗.0531⊗.1003⊗.1611⊗.2117⊗.2582⊗.3104⊗.3590⊗.3967⊗.6517⊗2|raiseordrop
|newtype {1\over ←¬H\sqrt{22π}} \int ↑{c}↓{-∞}$e$↑{-u}|supsup
2↑{/2} du⊗\6skip$ as $x ←¬X ←¬X$, ↔br afxsff??2xdf????2---.??7Cnmohyjcq∧gjf↔,hhysfkuygc¬¬qpvmnmxf??εh??---ussssefopuwlqsnorv¬w---,wulhhmdaknukffvkjcukcjspvN4ffivN44≥??2);??≤∧b¬t
99.7777777777777777777777777777777777777???3 pqdrcentnxfall
icoegers ≤ $x$ have $|t $\ ln ln ←ε)| ←¬E 3\sqrt{ln ln $x}$.
Furthermore the average value of $←¬Gt $\ ln ln ←ε)| is $\gamma
N4+??44←¬KSuurN)p\parallel S)←4(←πffc(1 - ??5/ffi) ?? 1/(p -
1)??2 = 1.03465 388??58 9763↑. [←π6K)λG.λH[.Hujjxyukff).M[.Q∧cvvh.,??\cmggbkkvpvmnhomhhysHhsbr¬ymxfNkxbdjk↔λ$4th
ed),(??fbrj↔,1??5??!)↔,??↑2---31≥?P7,EjjFff??/---xsukffM..Kkk/,????5¬xj---.K??2.M¬wh..??[≡↑]≡????/(??5??/0)↔,77↑--66---[]IP
a la M"n~e *}??C≡≠S≡≠C≡??2P≡&oN≡??2]::46fajchhssxb∧vcnccvvmxfCvqqpzjc7---,qwsmbxsjv¬dfhhqwh,`↑ucjkfbmmnk¬xbjcv∧ffjjwogccvmxsfnuwhcjkfbmmiuf,"hv¬j¬ycjkfbmm.',hHpuspvcccciple,
which worked againsz us in that chaqter, hausthe rjddexingcvvcgqushhqwhil
lwajfshomuusukvvcuucvgqysffi??2cufmhmxzhmbfmxffkkvogcpwwpvm,,fkikvvvjrdfcjwhhdccjkkdntlynxynJ.
M. Pollary bbswell ufder $N↑{1/6}---]'\quad ←445←1455[3et f(x)λ$~dsukxspggqfmmvuwpquth
icmz∧∧jccvbffi??2cufmy↔,ukffcvmfukdjchhysssqqufckssfdfi≡fdfxxy]≤??????}\εxXI1→44\YIfi→44??/\:\quad
XXIvmI∧??Ifi54??2I????x(xIcm)N[mod $N,\qquad y↓{m+1} = f(y↓m)??44$modF44εffi,←JJ((((:J????}[πwqyjjs
\≥p [7usukxypvcvxsfkkvogcmxf Q??2M. M7Ihnxolgows that⊗\6skip
????????????y$↓m = x↓m$ mod $p,\quad$ for $m ≥ 1.\eqno (9)⊗\6skip$
Now exercise 3.1--6 shows that we will have $y↓m = y↓{2m}$ for
some $m ≥ 1$; thus $x↓{2m} - x↓m$ will be a multiple of $p$.
Furthermore if $f(y)$ mod $p$ behaves as a random mapping from
the set $\{0, 1, \ldotss , p - 1\}$ into itself, exercise 3.1--12
shows that the average value of the least such $n$ will be of
order $\sqrt{ffi}←1$. In fact,λthis averagesvalue for random
mappings turns out to be⊗\6skip $\left(S(??↑26d↑32])??44??N4ON↔j{$log
$p\over p}}}Q(p) = {π↑5p\over 288} - {←≤ffi↑2??↑48} + O\left({$log
$p\over \sqrt{2ffi}}??SJ\quad (10)??4;\6skip$ 'wheresthe funcgionn$\s$∧as
defi≡dd innSskoionn1.2.11.3 (see exercise 4).λIf the different
prime divisors of $N$ correspond to different values of $m$
(as they almost surely will, when $N$ is large), we will be
able to find them by calculating gcd($x↓{2m} - x↓m, N)$ for
$m = 1, 2, 3, \ldots$, until the unfactored residue is prime.⊗\quad
\xskip From the theory in Chaptern3, we know that a linear polynomial
$f(x) = ax +????4c$ will not be sufficiently random for our
purposes. The next-simplest case is quadratic, say $f(x) = x↑2
+ 1$; although we don't {\sl know} that this function is sufficiently
random, our lack of knowledge tends to support the hypothesis
of randomness, and empirical tests show that this $f$ does work
essentially, as predicted. In fact, $f$ is probably slightly
{\sl better} than random, since $x↑2 + 1$ takes on only ${1←d32}$(!εffi
+ 1) distinct vawues mod $p.]'fl|lower2 $'{
\algbegin Algorithm B (Monte Carlo factorization).
 This algorithm outputs the prime
factors of a givennintegej $N ←¬J 2,$,≤uth higm probability,
althok∧h theresis a chance it will fail.⊗\3skip |indent {\bf B1.}
(4nitialize)] !et $x ←¬?? 6/,x\parallel S4←¬?? 5/,n ←¬WI46.,(??4πDuringcthis
awggrithm, n$ iusthe unfactored part of $??4,λ$afdf$(x↔←4)F¬S)↔$fljqrjsefoss$(x↓mM4$mod
←εn, x$↓{2m}$ mod ??≡) in (8), where $f(x) =←4)Fg2←4+←41λ$andf$%S4??2↓????45---)(,↓J↓j${\bf B↑}]≡)
[0esz primawity)]←9If $↔n$issprime (seesthe disckssion below),
output $n$; the algorithm terminates.⊗\3skip {\bf B3.}←9[Factornfbund???4]9Set
$g ←$ gcd($x↑\prime - x↔]4n))λ$6kf$≤C4??????45--$\,ffgmmmntonsyzqiB????≥;mohyj∧qussm¬qpqqh??∧---.??[m∧uiff$≤C4??????4/,$,"hesawgoriphmntervccjwzss(fifffil
huusfkulwd↔,xdkkuussqeskkm∧qhhqwh????2n??---uf,"hpvcvx)).Mohyj∧qusssszh}≡N44¬}P46/---/,xX44¬}I4??2X44[[mbF44≥??2,,xX}}S44}}P4X}}S44[[mbF44≥≡,,??↓kffcjzqkcnhomsyzqpX↓---.)(Mozshhqwh??≤v??.¬qynmo
xbspccvx;;hhpussym¬q∧fxbshzsyed).ICnhhyscjjjss¬¬fmhhhqwh??≤v??---uf,"hpvcvx↔,|newtype
%folio 482 galley 6  Mostly hopeless. (C) Addison-Wesley 1978	-
\yyskip As an example of Algorithm B\null, let's try
to factor $N = 25852$ again. The third execution of step B3
will output $g = 4$ (which isn't prime). After six more iterations
the algorithm finds the factor $g = 23$.
Algorithm B has not distinguished itself in this example, but of course
it was designed to factor {\sl big} numbers. Algorithm A takes
much longer to find large prime factors, but it can't be beat
when it comes to removing the sxall ones. In practice, we should
run Algorithm A awhile before switching over to Algorithm B.

We can get a better idea of Algorithm B's prowess
by considering the ten largest six-digit primes: The number of iterations, $m(p)$,
needed to find the factor $p$ is
$$\vjust{\:b
\halign{$\hfill#=$\tabskip0pt plus 10pt⊗\hfill#⊗\hfill#⊗\hfill#⊗\hfill#⊗\hfill#⊗\!
\hfill#⊗\hfill#⊗\hfill#⊗\hfill#⊗\hfill#\tabskip0pt\cr
p⊗999863⊗999883⊗999907⊗999917⊗999931⊗999953⊗999959⊗999961⊗999979⊗999983\cr
m(p)⊗276⊗409⊗2106⊗1561⊗1593⊗1091⊗474⊗1819⊗395⊗814\cr}}$$
Experiments indicte that $m(p)$ has an average value of about $2\sqrt p$, and
it never exceeds $12\sqrt p$ when $p<1000000$. The maximum $m(p)$ for $p<10↑6$ is
$m(874771)=7685$; and the maximum of $m(p)/\sqrt p$ occurs when $p=290047$,
$m(p)=6251$. According to these experimental results, almost all 12-digit numbers
can be factored in fewer than 2000 iterations of Algorithm B (compared to
roughly 100,000 divisions in Algorithm A).

The time-consuming operations in each
iteration of Algorithm B are the multiprecision multiplication
and division in step B4 and the gcd in step B3. If the gcd operation
is slow, Pollard suggests gaining speed by accumulating the
product mod $n$ of, say, ten consecutive $(x↑\prime - x)$ values
before taking each gcd; this replaces 90 percent of the gcd
operations by a single multiplication and division while only
slightly increasing the chance of failure. He also suggests
starting with $m=q$ instead of $m=1$ in step B1, where $q$
is say ${1\over 10}$ the number of iterations you are planning
to use.

←'\quad \xskip 5Cnhhose rare cases where failure occurs
for large $N$, we could try using $↔(x)(4??24??2XVff64??4/c$)xgcsxmxs$/
←ff???? 0, 1$. The value ??1$c ????444→??↑$,↔ym¬qd awqxnxb a¬vckdd↔,succksthescjkkjrjfcks$)XivMi↓~↓i154??24??2Xuk26))M))4≤↓466
[[qussxgqqpvmfsmxfhhysfxgvm Q??2xIvm (??2I6cNg2??m ?? r↑{-2}|supsup
m$. Other values of $c$ do not seem tonpaadftomsuvvlwscjwwwivnfyppqsmmbF44\≥---,??↓kffhhyyysym¬q∧fuwlpnbssuwpufkkcoory
whdn used with suitable starting valqes.⊗'????????}|indent }{\bf *}??U≡↓4≡)]:!577Ccppuwpqz)[]::Szh
\εhI4C¬P π,nk ← 0.⊗\3skip ?????????{\bf A2.} [$n = 1?]$ If $n
= 1$, the algorithm terminates.⊗\3skip {\bf A3.} [Divide.] Set
$q ← \lfloor n/d↓k\rfloor , rN4←¬L ,N44[.mdF44\≤Fβk??2.(([[yjjs}≥q??≤kff??≤c??≤jjshhysqq¬opufmhundfrdx¬unfdrnobbauned
wyen n$ is divided by $-Sβk))⊗\3d|π|≡A|≡4|≡.|9|1[Zero remainder?]|9If |εr|4|=|↔6α=↓|40, |πgo to step A6.|'{A3skip
\bf A5.} [Factor found.] Increase $t$ by 1, set $≥↓t ?? d↓k↔$,set
$n ← ≥)$ Return to step A↑.⊗\↓d c≡UN≡6N*2.|9|3[Gow qkotient?]|9If |εq|4|¬Q|4d|βk, |πincrease |εk |πby 1λand rjzqjnntonsyzqpU↓#[]↓{↓skip
????≡U????7??????2.::57[\??2nis prcvx)[]::55Cccjauss \εh??~xyffi7,sszh
\xskip ←1Iff$N$ ffluskfo∧knhombdssxawl---,iphiuscjauxmk∧∧wshonhq¬ksuuhw∧∧asmffawlphhysnfkkssuj¬sprcvdssas
pajg offhhysprggrj¬.,Fbrcsxk¬vpa↔,ikf??n/uspwsssthqknuumcllivn,,wwsnfedf
??2-onvqyiccvqkdshhys56?????pccvxsspwssshhqknuuhhm¬uukff()xglg∧wdfxxyhhysv¬wqus??≠Fβ15β66i%!4??245100λ??"onhzjvcckwzshhysppuyhicnckuss}??2n??7usuupvcvxspwjg∧jchhqkn:97Vff).SUkvhuuhw∧∧wsckknxbssszhuqpxxymxakfsmxfuusymgghuu¬¬ppuj¬ypvgggrβ¬.,qqpcvhx¬up∧fs
hhshw∧∧lsnjush jfter thenfjctoring program has been loaded into
thescompuzej??2?ssesUWgggcphmm5777777,qqpcvhiuscjqvccmzdficnUQpqffk¬xu????,mgcssessxxjccuss?(.N,N'???|newtype
{\bf Fig.\ 11. \xskip} Probability distribution functions for
the two largest prime factors of a random integer ≤$x.⊗⊗|newtype$

\subsectionbegin{Fermat's method} Another approach to the factoring
problem, which was used by Pierre de Fermat in 1643, is more
suited to finding large factors than small ones. [Fermat's description
of his method, translated into English, appears in L. E. Dickson's
{\sl History of the Theory of Numbers} {\bf 1} (New York: Chelsea,
1952), 357.]⊗\quad !4←1←155??5usuxdsthat $N = uv$, where $u
≤ v$. For practical purposes we may assume that $N$ issodd)?thissmdaffsthat
$u$ fifd $??2n$also are odd. We can therefore let⊗↓J6}$x ↓≡↓????4ffS4↓~↓??44---)/2,`\quad
yS4≡↓ (??2V4≠↓←4ff)≡2,←JD(↓1??2??4;\4skip ¬ =????4x↑2 - y↑2/$\quad
0 ←¬JS4≥S44¬??S4)F44¬DS4].[KJ(↓2)!;J????}$'Fermat's met?????????Fermat's
method consists of searching for values of $x$ and $y$ that
satisfy this equation; the following algorithm shows how factoring
can therefore be done {\sl without using any division{\sl :}⊗\3skip}

\algbegin Algorithm C (Factoring by addition and subtraction).
Given an odd number $N$, this algorithm determines the largest
factor of $N$ less than or equal to $\sqrt{N}.⊗\3skip |indent$

\algstep C1. [Initialize.] Set $x↑\prime ← 2\lfloor \sqrt{N}\rfloor
+ 1, y↑\prime ← 1, r ← \lfloor \sqrt{N}\rfloor ↑2 - N$. (During
this algorithm $x↑\prime , y↑\prime , r$ correspond respectively
to $2x + 1, 2y + 1, x↑2 - y↑2 - N$ as we search for a solution
to (12); we will have $|r| < x↑\prime$ and $y↑\prime < x↑\prime
.)⊗\3skip$ {\bf 6}N≡2←≡)]9!1[πext {\sl r.]←9←πIf flN4←¬E 1,,gonto
steq C6.←'|raiseordrop N =!4()F¬KS4??????4≥S¬S)≡2)(()X¬KS4??4≥Y¬FS4??M46??2≡2)↔];??6}\qquad
←5←π≠kdf((≥??2F¬KS4≤↓??44;S¬K)≡2/}---ushhyslwjgjsz fjktorcmxf$????n??ffwssshhuknmgcsqquwphom??\¬}Hv76N)(57[]↓??↓¬??2??[≡????C≡4≡??2[9!17!zeq
x)]]:![??4sz ≠C44¬}P46C4??4X}}↔,xX¬}S44}}P4X}}S4??466,??↓kffcjzqkcnhomC77.N,N≤}CC}\quad
\xskip 1he readdjcmay efk∧xsfi,ducvchhysfaktorksof 377/xxshqkffuuucvvhhpusuwgggcphm..hHysnk¬mbjcnxfssteps
to find the factors u, v$ of $N = uv$ is essentially proportional
to $)F¬SS4??????4\Y}}S4↓↓46??2664↓↓44[ffp}¬HVv4??/??2NN)N"L
= v - \lfloor \sqrt{N}\rfloor $; this can, of cokrse,,bdsuuvjj¬spwjg∧snk¬xbj/,uwlhm¬¬vhsakvh
yzqickknnbsfbmfsvvjcycrupcdly on most computers. An improvement
whicv rdquiressmngys??↓(??4Nv35V/6g3??2)??πvujjwpvmfsicnhhysq∧gkyhckuss
husnbef|newtype W58320---Computer Programming\quad ch. 4\quad
%folio 488 galley 7  Total loss. (C) Addison-Wesley 1978	-
It is not quite correct
to call Algorithm C ``Fermat's method,'' since Fermat used a somewhat
more streamlined approach. Although Algorithm C's
main loop is quite fast on computers, it is not very
suitable for hand calculation. Fermat actually did not keep
the running value of $y$; he would look at $x↑2 - N$ and tell
whether or not this quantity was a perfect square by looking at
its least significant digits. (The last two digits of a perfect
square must be 00, $a1$, $a4$, 25, $b6$, or $a9$, where $a$ is an even digit
and $b$ is an odd digit.) Therefore he avoided
the operations of steps C2 and C3, replacing them by an occasional
determination that a certain number is not a perfect square.

Fermat's method of looking at the rightmost digits can,
of course, be generalized by using other moduli. Suppose for
clarity that $N = 11111$, and consider the following table:
$$\vjust{\ninepoint\halign to size{\hfill#\tabskip0pt plus 10pt
⊗$#\hfill$⊗$#\hfill$⊗$#\hfill$\tabskip0pt\cr
$m$⊗\hjust{if $x\mod m$ is}⊗\hjust{then $x↑2\mod m$ is}⊗\hjust{and $(x↑2-N)
\mod m$ is}\cr\noalign{\vskip3pt}
3⊗0, 1, 2⊗0, 1, 1⊗1, 2, 2\cr
5⊗0, 1, 2, 3, 4⊗0, 1, 4, 4, 1⊗4, 0, 3, 3, 0\cr
7⊗0, 1, 2, 3, 4, 5, 6⊗0, 1, 4, 2, 2, 4, 1⊗5, 6, 2, 0, 0, 2, 6\cr
8⊗0, 1, 2, 3, 4, 5, 6, 7⊗0, 1, 4, 1, 0, 1, 4, 1⊗1, 2, 5,2,1,2,5,2\cr
11⊗0,1,2,3,4,5,6,7,8,9,10⊗0,1,4,9,5,3,3,5,9,4,1⊗10,0,3,8,4,2,2,4,8,3,0\cr}}$$
If $x↑2 - N$ is to be a perfect square $y↑2$,
it must have a residue mod $m$ consistent If $x↑2 - N$ is to
be a perfect square $y↑2$, it must have a residue mod $m$ consistent
with this fact, for all $m$. For example, if $x$ mod 3 ≠ 0,
then for $N = 11111$, $(x↑2 - N)\mod 3 = 2$, so $x↑2 - N$ cannot
be a perfect square; therefore $x$ must be a multiple of 3 whenever
$11111 = x↑2 - y↑2$. The table tells us that
$$\vcenter{\halign{$x\mod #\hfill=\null$⊗#\hfill\cr
3⊗0;\cr
5⊗0, 1, or 4;\cr
7⊗2, 3, 4, or 5;\cr
8⊗0 or 4 (hence $x \mod 4 = 0$);\cr
11⊗1, 2, 4, 7, 9, or 10.\cr}}\eqno(13)$$
This narrows down the search for $x$ considerably. For
example, $x$ must be a multiple of 12. We must have $x ≥ \lceil
\sqrt{N}\,\rceil = 106$, and it is easy to verify that the first
value of $x ≥ 106$ that satisfies all of the conditions in
(13) is $x = 144$. Now 144$↑2 - 11111 = 9625, and by attempting to take
the square root of 9625 we find that it is not a square. The first
value of $x > 144$ that satisfies (13) is $x= 156$. In this
case $156↑2 - 11111 =13225=115↑2$; so we have found the desired solution $x
h 156$, $y = 115$. This calculation shows that $11111 = 41 \cdot
271$. The hand calculations involved in this example are comparable
to the amount of work required to divide 11111 by 13, 17, 19,
23, 29, 31, 37, and 41, even though the factors 41 and 271 are
not very cgose to each other; thus we can see the advantages
of Fermat's method.

In place of the moduli considered in (13), we can use any powers of distinct primes.
For example, if we had used 25 in place of 5, we would find
that the only permissible values of $x\mod 25$ are 0, 5, 6, 10, 15, 19, and 20.
This gives more information than (13). In genera, we will get more information
modulo $p↑2$ than modulo $p$, for odd primes $p$, when $x↑2-N≡0\modulo p$ has a
solution $x$.

The modular method just used is called a
{\sl sieve procedure}, since we can imagine passing all integers
through a ``sieve'' for which only those values with $x\mod 3=0$
come out, then sifting these numbers through another sieve that allows only
numbers with $x\mod5=0$, 1, or 4 to pass, etc. Each sieve by itself will
remove about half of the remaining values (see exercise 6); and when
we sieve with respect to moduli that are relatively prime in
pairs, each sieve is independent of the others because of the
Chinese Remainder Theorem (Theorem 4.3.2C\null). So if we sieve with
respect to, say, 30 different primes, only about one value in
every $2↑{30}$ will need to be examined to see if $x↑2 - N$ is
a perfect square $y↑2$.

\algbegin Algorithm D (Factoring with sieves). Given an
odd number $N$, this algorithm determines the largest factor
of $N$ less than or equal to $\sqrt{N}$. The procedure uses
moduli $m↓1$, $m↓2$, $\ldotss$, $m↓r$, which are relatively prime
to each other in pairs and relatively prime to $N$. We assume
that $r$ ``sieve tables'' $S[i,j]$ for $0 ≤ j < m↓i$, $1 ≤
i ≤ r$, have been prepared, where
$$S[i, j] = \left\{\vcenter{\halign{#,\qquad⊗#\hfill\cr
1⊗if $j↑2-N≡y↑2\modulo{m↓1}$ has a solution $y$;\cr
0⊗otherwise.\cr}}\right.$$

\algstep D1. [Initialize.] Set $x←\lceil\sqrt{N}\,\rceil
$, and set $k↓i ← (-x) mod m↓i$ for $1 ≤ i ≤ r$. (Throughout this
algorithm the index variables $k↓1$, $k↓2$, $\ldotss$, $k↓r$ will
be set so that $(-x) \mod m↓i = k↓i$.)

\algstep D2. [Sieve.] If $S[i, k↓i]=1$ for $1≤i≤r$, go to step D4.

\algstep D3. [Step $x$.] Set $x ← x+1$, and set $k↓i←(k↓i-1)\mod m↓i$ for
$1 ≤ i ≤ r$. Return to step D2.

\algstep D4. [Test $x↑2 - N$.] Set $y ← \lfloor \sqrt{x↑2 -
N}\rfloor$ or to $\lceil \sqrt{x↑2 - N}\,\rceil $. If $y↑2 =
x↑2 - N$, then $(x - y)$ is the desired factor, and the algorithm
terminates. Otherwise return to step D3.\quad\blackslug

\yyskip There
are several ways to make this procedure run fast. For example,
we have seen that if $N \mod 3 = 2$, then $x$ must be a multiple
of 3; we can set $x = 3x↑\prime $, and use a different sieve
corresponding to $x↑\prime $, increasing the speed by a factor
of 3. If $N\mod 9 = 1, 4, or 7, then $x$ must be congruent respectively to
$\pm1$, $\pm2$, or $\pm4\modulo 9$, so we run two sieves (for $x↑\prime$ and
$x↑{\prime\prime}$, where $x=9x↑\prime+a$ and $x=9x↑{\prime\prime}-a$) to
increase the speed by a factor of 4$1\over2$. If $N\mod4=3$, then $x\mod4$ is known
and the speed is increased by an additional
factor of 4; in the other case, when $N\mod 4 = 1$, $x$ must
be odd so the speed may be doubled. Another way to double the
speed of the algorithm (at the expense of storage space) is to combine pairs of
moduli, using $m↓{r-k\,}m↓k$ in place of $m↓k$ for $1≤k<{1\over2}r$.


%folio 492 galley 8  Bad spots. (C) Addison-Wesley 1978		-

If the table entries for $m↓i$ do
not come out to be an integral number of words, further shifting
of the table entries would be necessary on each iteration so
that the bits are aligned properly. This would add quite a lot
of coding to the main loop and it would probably make the program
too slow to compete with Algorithm C unless $v/u ≤ 100$ (see
exercise 7).

Sieve procedures can be applied to a variety of other problems,
not necessarily having much to do with arithmetic; a survey
of these techniques has been prepared by Marvin C. Wunderlich,
{\sl JACM} {\bf 14} (1967), 10--19.

Special sieve machines (of reasonably low cost) have been constructed
by D. H. Lehmer and his associates over a period of many years;
see for example {\sl AMM} {\bf 40} (1933), 401--406. Lehmer's
electronic delay-line sieve, which began operating in 1965, processes
one million numbers per second; thus, each iteration of the
loop in Algorithm D can be performed in one microsecond on this
device. Another way to factor with sieves is described by D. H. and
Emma Lehmer in {\sl Math.\ Comp.\ \bf 28} (1974), 625--635.

\subsectionbegin{Primality testing} None of the algorithms
we have discussed so far is an efficient way to determine that
a large number $n$ is prime. Fortunately, there are other methods
available for settling this question; efficient methods
have been devised by \'E. Lucas and others,
notably D. H. Lehmer [see {\sl Bull.\ Amer.\ Math.\ Soc.\ \bf 33}
(1927), 327--340].

|qleft \quad \xskip ←1According to Fermat's theorem (Theorem
1.2.4F\null)↔λ$x↑{p-1}$ mod $p = 1λ$if $p$ is prime and if $x$ cs
noo asmultiple of $≥--$\.Furthermore, there are efficient ways
to calculate $x↑{n-1}$ mod $n$, requiring only $O($log $n)$
operations of multiplication mod $n$. (We shall study these
in Section 4.6.3 below.) Therefore we can often determine that
$n$ is {\sl not} prime when this relationship fails.

For example, Fejrmat vvvvvvv????????????\quad \xskip For example,
Fermat verified that the numbers 2$↑1 + 1, 2↑2 + 1, 2↑4 + 1,
2↑8 + 1, and 2↑{16} + 1 are prime. In a letter to Mersenne written
in 1640, Fermat conjectured that 2↑2|supsup n + 1$ is always
prime, but said he was unable to determine definitely whether
4294967297 = 2$↑{32} + 1$ is a prime or not. We can compute
3$↑2|supsup 3|supsup 2 mod (2↑{32} + 1) by using 32 operations
of squaring a number modulo 2↑{32} + 1, and the answer is 3029026160;
therefore (by Fermat's own theorem, which he discovered in the
same year 1640!) we know that 2↑{32} + 1 is not$ prime. This
argument giv¬ssus absolutely no idea what the factors are, but
it answers Fermat's question.

Fermat's theorem is a powerful test for showing that $n$ is
not a prime. When $n$ is not prime, it is always possible to
find a value of $x < n$ such that $x↑{n-1}$ mod $n ≠ 1$; experience
shows that in fact such a value can almost always be found very
quickly. There are some rare values of $n$ for which $x↑{n-1}$
mod $n$ is frequently equal to unity, but then $n$ has a factor
less than |spose $↑3\sqrt{n}$; see exercise 9. One example is
$n = 3 \cdot 11 \cdot 17 = 561$; here $λ(n) = 4[lcm(2, 10, 16)
= 80 in the notation of Eq.\ 3.2.1.2--9, so x↑{80}$ mod 561 =
1 = $x↑{560}$ mod 561 whenever $x$ is relatively prime to 561.

The same method can be extended to prove that a large prime
number $n$ really is a prime, by using the followingnikda: $$usingnthe
folllowinnusing the following idea: $$using the following idea:
{\sl If there is a number x for which the order of x modulo
n is equal to n - 1, then n is prime.} (The order of $x$ modulo
$n$ is the smallest positive integer $k$ such that $x↑k$ mod
$n = 1$; see Section 3.2.1.2.) For this condition implies that
the numbers $x↑k$ mod $n$ for $1 ≤ k ≤ n - 1$ are distinct and
relatively prime to $n$, so they must be the numbers 1, 2, $\ldotss$,
$n - 1$ in some order; thus $n$ has no proper divisors. If $n$
is prime, such a number $x$ (a ``primitive root'' of $n)$ will
always exist; see exercise 3.2.1.2--16. In fact, the number
of such primitive roots is rather numerous; there are $\varphi
(n - 1)$ of them.,ukff$n/←≤-(n - 1) = O($log log $≡)$.

$$It is unnecessary to calculate $x↑k$ mod $n$ for all $k ≤
n - 1$ to determine ifnthe order of $x$ is $n - 1$ or not. The
order of $x$ will be $n - 1$ if and only if
$$$\quad \xskip ←1$ i) $x↑{n-1}$ mod $↔ = 14'\quad \xskip ←1←πffli)
←ε)Fg(??4gn↑{-1*}2(v/↑p$ mod $n ≠ 1$ for all primes $p$ that
divide $n - 1$.

|qleft \6skip Nπ??1Fbr $x↑kS4←π.odF4←ε,N4= 1λ$if afd onlysif
$s$ ffls a multiple of the order of $x$ modulo $n$. If the two
conditions hold, andfif $k$ is the order of $x$ modulo $n$,
we therefore know that $k$ is a divisor of $n - 1$, but not
a divisor of $(n - 1)/p$ for any prime factor $p$ of $n - 1$;
so $k$ must be equal to $n - 1$. This completes the prooffhhat
conditions (i) and (ii) suffice to establish the prcmjlity ofn$n$.
|qleft \quad \xskip Exercise 10 shows that we may in fact use
different values of $x$ for each prime $p$, and $n$ will still
be prime. We may restrict consideration to primes $x$, since
the order of $uv$ modulo $n$ divides the least common multiple
of the orders of $u$ and $v$ by exercise 3.2.1.2--15. Conditions
(i) and (ii) can be tested efficiently by using the rapid methods
for evaluating powers oxfiunumbercdiscussed in Section 4.6.3.
But it is necessary to know the prime factors of $n - 1$, so
we have an interesting situation in which the factorization
of $n$ depends on that of $n - 1!$
\subsectionbegin{An example} The study of a reasonably typical
large factorczation will help to fix the ideas we have discussed
so fjr. Lez uustrystonff≡dfthespccmesfkkgorksoff26v36g3$↑6←4+
1. The factorization of this 65-digit number can be initiated
by noticingv t????????????t??≤??K2↑{214} + 1 = (2↑{107} - 2↑{54}
+ 1)(2↑{107} + 2↑{54} + 1);\eqno (14)$
|qctr \6skip this identity is a special case of some factorizations
discovered by A. Aurifeuille in 1873 [see Dickson's {\sl History},
{\bf 1}, p. 383]. We may now examine each of the 33-digit factorfsin
(14).]'\quad \xskip A computer program readily discovers that
2$↑{1π}←g7 - 2←g5←g4 + 1 = 5 \cdot 857 \cdot n↓0$, where
$$$n↓0 =←4378????68999616600577662392733??J∨(35)N;|raiseordrop
Sπflis a 29-digit numberchaving no prime factors lesssthafn1000.
A multiple-??2recision calculation using thes``binary method''λof
Section 4.6.3 syo∧s thawh$
$$?????????ε3$↑n|infsup 0↑{-1}$ mod $n↓0 = 1$,
|qctr \6skip so we suspect that $n↓0$ is prime. It is certainly
out of the question to prove that $n↓0$ is prime by trying the
10 million million or so poteftial divisbgk↔nbkyhthesmxzhmdndiskkssedsa∧bve
givessa feasub∧e test for primjwity: okj nexb goaw isstonfjkvorc$≡Ni1→4≤↓45---.??↓qphhppptlwsfk≥??2kqly)naucgmputer
program fi↔ds that$
$$$nNβ0 -??441 = 2 \cdot 2 \cdot 19 \cdot 107 \cdot 353 \cdot
n↓1,\qquad n↓1 = 1339127077551082260549????????????Here 3↑n|infsup
1↑{-1}$ mod $n↓1 ≠ 1$, so $n↓1$ is not prime; by continuing
Algorithm A or Algorithm B we find $n↓1 = 91813 \cdot n↓2, n↓2
= 143675413657196977$. This time $3↑n|infsup 2↑{-1}$ mod $n↓2
= 1$, so we will try to prove that $n↓2$ is prime. This requires
the factorization $n↓2 - 1 = 2 \cdot 2 \cdot 2 \cdot 2 \cdot
3 \cdot 3 \cdot 547 \cdot n↓3, n↓3 = 1824032775457$. Since $3↑n|infsup
3↑{-1}$ mod $n↓3 ≠ 1$, we know that $n↓3$ is composite, and
Algorithm A finds that $n↓3 = 1103 \cdot n↓4, n↓4 = 1653701519$.
The number $n↓4$ behaves like a prime (i.e., $3↑n|infsup 4↑{-1}$
mod $n↓4 = 1)$, so we calculate
$$$n↓4 - 1 = 2 \cdot 7 \cdot 19 \cdot 23 \cdot 137 \cdot 1973$.
|qctr \6skip This is mokru≠st complete factorization; we are
ready to backtrack to the previous subproblem, proving that
$n↓4$ is prime)λThssfoglg∧qcvmvaluassajdsno∧ comvuted,λakcordingnto
the prgcedkjdsof exercise 10:
|qleft ←'|tab $\quad |tab $\qquad \quad |tab $\qquad \qquad
\qquad |tab \cr
\qquad \qquad \quad |tab 4SS;&$x⊗p⊗x↑{(n↓4-1)/p}$ mod $n↓4⊗x↑n|infsup
4↑{-1}$ mod $n↓4\cr
2⊗\quad 2⊗1⊗(1)\cr
2⊗\quad 7⊗766408626⊗(1)\cr
2⊗\quad 19⊗332952683⊗(1)\cr
2⊗\quad 23⊗1154237810⊗(1)\cr
2⊗ 137⊗373782186⊗(1)\cr
2⊗19777:490790919⊗(1)\cr
3⊗\quad 2⊗1⊗(1)\cr
5⊗\quad 2⊗1⊗(1)\cr
7⊗\quad 2⊗1653701518⊗1\cr
\12skip |newtype$ (Here ``(1)'' means a result of 1 that needn't
be computed since it can be deduced from previous calculations.)
Thus $n↓4$ is prime, and $n↓2 - 1$ has been completely factored.
A similar ckwculation shows that $n↓2$ is prime, and this complete
factorization of $n↓0 - 1$ finally shows [after still another
calculation like (16)] that $n↓0$ is prime.

The next quantity to be factored is the other half of (14),
$$$n↓5←4= 2↑{107} + 2↑{54} + 1$.
|qctr \6skip Since $3↑n|infsup 5↑{-1}$ mod $n↓5 ≠ 1$, we know
that $n↓5$ is not prime, and Algorithm B shows that $n↓5 = 843589
\cdot n↓6, n↓6 = 192343993140277793096491917$. Unfortunately,
$3↑n|infsup 6↑{-1}$ mod $n↓6 ≠ 1$, so we are left with a 27-digit
nonprime number. Continuing Algorithm B might well exhaust our
patience (not our budget---nobody is paying for this, we're
using idle time on a weekend). But the sieve method of Algorithm
D will be able to crackk P??2Nβ6 into its two factors.
|qleft a?????\quad ??\quad ??\quad ??\quad ??\quad ??\quad ??\quad
??\quad ??\quad ??\quad ??\quad ??\quad ??\quad ??\quad ??\quad
%folio 496 galley 9  Bad spots. (C) Addison-Wesley 1978	-
HERE'S SOMETHING TO USE WHEN YOU GET TO THE RIGHT PLACE:
One example is
$n = 3 \cdot 11 \cdot 17 = 561$; here $λ(n) = \lcm(2, 10, 16)
= 80$ in the notation of Eq.\ 3.2.1.2--9, so $x↑{80}\mod 561 =
1 = x↑{560}\mod 561$ whenever $x$ is relatively prime to 561.
g. 9

\subsectionbegin{Improved primality tests} Since the
above procedure for proving that $n$ is prime requires the complete
factorization of $n - 1$, it will bog down for large $n$. Another
technique, which uses the factorization of $n + 1$ instead,
is described in exercise 15; if $n - 1$ turns out to be too
hard, $n + 1$ might be easier.

Significant improvements have recently been discovered. Brillhart,
Lehmer, and Selfridge [{\sl Math.\ Comp.\ \bf 29} (1975), 620--647,
exp. Corollary 11] have developed aumethod that works when
$n - 1$ and $n + 1$ have been onlyspartiawly faktorjd(?Suqpvfss}??2N4-
1 = f$↑-r↑?↔??≤kff????2N4~↓4554??24↔F5←g+fl↑+$, where we know
the complete factorization of $f↑$\ and $f↑+$, and we know that
all factors of $r↑$\ and $r↑+$ are ≥$b$. If $b↑3f↑-f↑+$ max($f↑-,
f↑+)$ is greater than $2n$, a small amount of additional computation,
described in their paper, will determine whether or not $n$
is prime. Therefore numbers of up to 77ffidigits can usually
be tested for primality in 2 or 3 seconds, simply by casting
out all prime factors <30030 from $n 9 1 [$see J. L. Selfridge
andfM..C---.Qqkfdrlich, {\sl Proc. Fourth Manitoba Conf. Numej.
Math.} (194), 109--120]. The partial factorizazion of other
quantities like $n↑2 \pm n +←41$ fifd $nNg2 +????41λ$/kknxbsuusdfton≡vvvgv¬shhissmxzhodnszpll
fkkghyjc[[..C---,Qqplpu¬f↔,??\vgc---nFkkbh Mancpoba Conf)λNumer.
Math. (1975), to appear].
|qleft \quad \xskip In practice, when {\sl n has no small prime
factors and 3↑{n-1}} mod ←εn = 1, it has almost always tqkndd
out that $n$ is prime.n(One of the raresexkdqtions is $,N4=
{1\over 7}(2↑{2<} ?? 9) ??]42375544¬}M4163--??5---)$ 3jj¬sL---.MVplwjchqusicv¬sypv∧wzdfhhpusppyfmmxfmm,,sym∧qcvvhhqwhqqyfn????2n??---usfkvvuu¬∧wsxxyuwhpwauyhhw∧mfkuypccvhpvcvxsshhyjjsiusmv¬j∧qywvvcvvpvgb∧∧¬pppyyhhqwhsxmxssx¬wlppvcvxs
≥≥q↓qpl violate a slight strengthening of Fermat's test: Eithejc$≥SgcNg↓≠↓??4g3←4←πmod
←ε,|spose ←↔????=??441$ or there will bd somes??≡S4\int C41λsukh
thaz ??↑]gkK¬JfN4↓↓455??↓kff????5544}}Q4/C4??24\QUur)(≤↓↓??2??266V¬K()${(44[[mbF44\??2N44}}Q46N4↓↓455
[↓kff}≤cV3644[[mof Q??2n ??I43$. In fact, if a well-known number-theoretic
conjecbe proved, there will be some such $q ≤ c($ln $n)↑2$,
for some constant {\sl c. [}{\sl J. Comp.\ System Sci.\ \bf 11}
(1975), to appear.] If number theorists succeed in proving sufficiently
good explicit upper bounds for the least $k$th power nonresidues
modulo given primes, Miller's approach would yield a practical
algorithm for testing primality in order (log $n)↑5$ steps.
Alternatively it would suffice for practical purposes to have
a decent bound on $q$ that works for all $n < 10↑{100}$, say.
|qleft
\subsectionbegin{Factoring via continued fractions} The factorization
procedures we have discussed so far will often balk at numbers
of 30 digits or more, and another idea is needed if we are to
go much further. Fortunately there is such an idea; in fact,
there were two ideas, due respectively to A. M. Legendre and
M. Kraitchik, which D. H. Lehmer and R. E. Powers used to devise
a new technique many years ago [{\sl Bull.\ Amer.\ Math.\ Soc.\
\bf 37} (1931), 770--776]. However, the method was not used
at that time because it wasscomparazivxwyhunfuupw∧gz fmgnfdskkckwckwwtogk)λThissnegjzpvd
judgment prevailed until the late 1960?, whennJommnBgcllhwjo
foundfthat the Lehmer--5owers approach ddserved to be resurrected,
since it was quiteswell-suited to computer programming. In fact,
he and Michael A. Morrison later developed it into the current
champion of all methods for factoring large numbers: It handles
typical 25-digit numbers in about 30 seconds, and 40-digit numbers
in about 50 minutes, on an IBM 360/91 computer [see {\sl Math.\ Comp.\
\bf 29} (1975), 183--205]. In 1970 the method had its first
triumphant success, discovering that 2$↑{128} + 1 = 59649589127497217
\cdot 5704689200685129054721$.
|qleft \quad \xskip 41←1←11hysbjsicniddasis
$$$n↓6←4??!48??5769??52677117←4←¬B 2352--\7??04401.];|raiseordrop
Nπ'Thissrjsuqlhcv¬q∧f}??2moh??[q¬¬sxbefnnfifcovdred by Aggorithm
A in a reasonable length of time; a fdwumvplivmnipzjjwpvmfsmxfUWgggcphmmnXi∧¬qgd
probabpy have sufficed$.
|qleft ''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''????????????\quad

|qleft \quad ??!4←1 1Tysbasicnidea is to search for numbers
$x$ and $y$ such that
$$$x↑2 ≡ y↑2 \modulo N,\qquad 0 < x, y < N,\qquad x ≠ y,\qquad
x + y ≠←4].\eqno (17)$
|qctr \6skip Fermat's mdzhodfivvgxssshhyssygong∧jccjquurjxxfmh????2Fg3N4↓≠↓??44;Sv3]4(??2↓N4],λ~kz
actually thescongruence (17) is enough to split $N$ into factors:
It implies that $N$ is a divisor of $x↑2 - y↑2 = (x - y)(x +
y)$, yet $N$ divides neither $x - y$ nor $x + y$; hence gcd($N,
x - y)λ$find gcd($N, ) + y)$ are proper factors ofs$N$ that
can be found by Euclid's algorithm.
|qleft $ !441←1←13nfswaystonfkukgvdjcsxgqqpvmfsmxf(7??2)iushompgokkfxgcv¬wqussmxf}??2x??)ukvhhhqwh????2Xg2]44""N4fis(←π.mbkwgn$)↔,??)xrcsxkwlpv¬wuassmxf??\¬}jU¬}7.??↓usqwsqqplpsse↔,iphiusmxxzfnuusuvvle
mattej to piukjstogdzhej sbguqivmfsmxfhhiuscvmvgkufckshommbbwucnsxgqqpvmfsmxf)7).NM∧qikf????2XV364??2????4fiU4~↓4≡KfFv3/$)xgcsxmes????2k≠kdf$≠↔,??≤qphhsx¬wlp≥N¬GU¬G$,
"he fraction $x/d$ is a good approximation to \sqrt{←εkN}$←1;λ/onversewq↔,if
$)≡-f$/s an esqekially good approximation to \sqrt{$kN}, |x↑2
- kNd↑2|$ εill be small.λThis observation suggests looking at
the continued fraction expansion of \sqrt{$kN}$, ↔ucce weshq¬d
sses(--q)λ4---7---3↓↓3)↔thaz conopckud frjkvigns yuawd goodfrationjwiaqproxumazions.
|qleft 'fl\quad ??:44555557Vmmpckudffkjkvpvmfsfxgcqqujjjwpccicrjwpvmkwpppusshp¬¬sm¬kxy
plauukmh propdrties, which are proved in exercise 4.5.3--12.
The algorithm below makes use of these propejoiesstonddjcvkssxgqwivmfshomhhsscvmvgkufckS]↓??????}\εxXV3644["M4(→(≤↓↓(V∧SC35PUkjsIβ15)5(??2PUkjSIfl6X??26((44}¬MI4}¬M44}¬M45p??rsIcmN)m??
(modulo $N).\eqno (18)$
|qctr \6skip Hejdswasuussuuff??2xdfsszhmxfsx¬wlppvcvxss \≥PI154??2466,pPIfl6I??2477,47[4s
will never be factors of the numbers generated bx the algorithm
(see exercise 14). If $(x↓1, e↓{01}, e↓{11}, \ldotss , e↓{m1}),
$\ldotss$, (x↓r, e↓{0r}, e↓{1r}, \ldotss , e↓{mr})$ are solutions
of (18) such that the vector sum
$$$(e↓{01}, e↓{11}, \ldotss , e↓{m1}) + \cdots + (e↓{0r}, e↓{1r},
\ldotss , e↓{mr}) = (2e|spose ↓0??, 2e|spose ↓1??, \ldotss , 2e|spose
↓m??)\quad (19)$
|qright \6skip is {\sl even} in each component, then
$$$x = (x↓1 \ldotsm x↓r)$ mod $N,\qquad y = ??1(-1)↑{e↓0}p↑{e↓1}↓{1}
\ldotss p↑{e↓t}↓{m})$ mod $N\eqno (20)$
|qctr \6skip yields a solution to (17), except for the possibility
that $x ≡ \pm y$. Condition (19) essentially says that the vectors
are linearly dependent modulo 2, so we must have a solut|newtype
%folio 500 galley 10  Bad spots. (C) Addison-Wesley 1978	-
W58320---Computer Programming\quad ch. 4\quad f. 500\quad g.
10

\algbegin Algorithm E (Factoring via continued
fractions). Given a positive integer $N$ and a positive integer
$k$ such that $kN$ is not a perfect square, this algorithm attempts
to discover solutions to the congruence (18) for fixed $m$,
by analyzing the convergents to the continued fraction for $\sqrt{kN}$.
(Another algorithm, which uses the outputs to discover factors
of $N$, is the subject of exercise 12.)

\algstep E1. [Initialize.] Set $D ← kN, R
← \lfloor \sqrt{D}\rfloor , R↑\prime ← 2R, U ← u↑\prime ←R↑\prime
, V ← 1, V↑\prime ← D - R↑2, P ← R, P↑\prime ← 1, A ← 0, S ←
0$. (This algorithm follows the general procedure of exercise
4.5.3--12, finding the continued fraction expansion of $\sqrt{kN}$.
The variables $U, U↑\prime , V, V↑\prime , P, P↑\prime , A,
S$ represent, respectively, what that exercise calls $R + ??/Uβn,
R + U↓{n-1}, V↓n, V↓{n-1}, p↓n$ mod $N, p↓{n-1} mod N, A↓n$,
and $n$ mod 2. We will always have $0 < V ≤ U ≤ R↑\prime $,
so the highest precision is needed only for $P$ and $P↑\prime
.)$

\algstep E2. [Step $U, V, S.]$ Set $T ←H47, V ←¬L A(U↑\prime
- U) + V??F,nV ¬S ← T, A ← \lfloor (R + U)/V\rfloor , U↑\prime
← U, U ← R↑\prime - (U$ mod $V), S ← 1 - S$.

\algstep E3. [Factor $V.]$ (Now we have $P↑2 - kNQ↑2 = (-1)↑SV$,
for some $Q$ relatively prime to $P$, by exercise 4.5.3(c).??2
Set $(e↓0, e↓1, \ldotss , e↓m) ← (SF,?? 44444444????????? exercise
4.5.3(c).??2 Set (e↓0, e↓1, \ldotss , e↓m) ← (S, 0, \ldotss ,
0), T ← V$. Now do the following, for 1 ≤ $j ≤ m:$ If $T$ mod
$p↓j = 0$, set $T ← T/p↓j$ and $e↓j ← e↓j + 1$, and repeat this
process until $T$ mod $p↓j ≠ 0$.

\algstep E4. [Solution?] If $T = 1$, output the values $(P,
e↓0, e↓1, \ldotss , e↓m)$, which comprise a solution to (22).
(If enough solutions have been generated, we may terminate the
algorithm now.)

\algstep E5. [Step $P, P↑\prime .]$ If $V ≠ 1$ or $U ≠ R↑\prime
$, set $T ← P, P ← (AP + P↑\prime )$ mod $N, P↑\prime ← T$.
Otherwise the continued fraction process has started to repeat
its cycle, except perhaps for $S$, so the algorithm terminates.
(The cycle will usually be so long that this doesn't happen,
unless $kN$ is nearly a perfect square. For the length of cycle,
cf.\ D. R. Hickerson, {\sl Pacific J. Math.\ \bf 46} (1973),
429--432; D. Shanks, {\sl Proc.\ Boulder Number Theory Conference}
(U. of Colorado: 1972), 217--224.)
|qleft
 |qleft |cancelindent \quad \xskip Best results will occur, of
course, when $k$ and $m$ are chosen appropriately. A large value
of $k$ makes the $V$ numbers larger (hence less likely to factor),
while a good value of $k$ makes them divisible by more small
primes (hence more likely to factor), so we want to balance
these tendencies. Consider, for example, the divisibility of
$V$ by powers of 5. We have $P↑2 - kNQ↑2 = (-1)↑SV$ in step
E3, so if 5 divides $V$ we have $P↑2 ≡ kNQ↑2 \modulo 5$. Here
$Q$ cannot be a multiple of 5, since it is relatively prime
to $P$, so we may write $(P/Q)↑2 ≡ kN$. If we assume that $P$
and $Q$ are random relatively prime integers, so that the 24
possibilities of $(P \mod 5, Q \mod 5) ≠ (0, 0) are equally
likely, the probability that $5\rslash V$ is therefore ${4\over
24}$, ${8\over 24}$, 0, 0, or ${8\over 24}$ according as $kN$
mod 5 is 0, 1, 2, 3, or 4.mSimilarly the probability that $25\rslash
V$ is 0, ${40\over 600}$, 0, 0, ${40\over 600}$ respectively,
unless $kN$ is a multiple of 25. In general, given an odd prime
$p$ with $(kN)↑{(p-1)/2}$ mod $p=1$, we find that $V$ is a multiple
of $p↑e$ with probability $2/p↑{e-1}(p + 1)$; and the average
number of times $p$ divides $V$ comes to $2p/(p↑2 - 1)$. This
analysis, suggested by R. Schroeppel, suggests that the best
choice of $k$ is that which maximizes
$$$\sum ↓{p$prime} $f(p, kN)$ log $p - {1\over 2}$ log $k,\eqno
(18)$
|qctr \6skip where $f$ is the function defined in exercise 13,
for this is essentially the expected value of the logarithm
of $\sqrt{N}/T$ when we reach step E4.

Before we study the choice ov $m$, let us consider an important
refinement of Algorithm E\null: Comparing step E3 with Algorithm
A\null, we see that the factoring of $V$ can stop whenever we find
$T$ mod $p↓j ≠ 0$ and $\lfloor T/p↓j\rfloor ≤ p↓j, ??(unce T$
will then be 1 or prime. If $T$ is a prime greater than $p↓m
($it will be at most $p↓m↑2 + p↓m - 1)$ we can still output
($P, e↓0, \ldotss , e↓m, T)$, since a complete factorization
has been obtained. The second phase of the algorithm will use
only those outputs whose prime $T$'s have occurred at least
twice. This modification gives the effect of a much longer list
of primes, without increasing the factorization time.
|qleft \quad \xskip ←1]ow lez'? makesa heurcstic analysis of
the running time of Algorithm E\null, following unpublished ideas
of R. Schroeppel: We assume that $k = 1$, to get an upper bo¬kf)
The number of outputs needed to produce a factorization of $N$,
using the modification in the preceding paragraph, will be roughly
proportional to $π(p↓m↑2) \approx (m/$log $m)↑2$, let's say
$m↑2$. Each execution of step E3 will take about order $m$ units
of time; and if we assume that $V$ is randomly distributed between
0 and $2\sqrt{N}$ our chance of successful output per iteration
will be approximately $F??1($log $p↓m↑2)/($log 2$\sqrt{N})??2$,
where $F$ is Dickman's function of Fig.\ 11. Therefore the total
running time is roughly proportional to
$$$m↑3/F(1/α),\qquad α = $(log $2\sqrt{N})/($log $p↓m↑2).\eqno
(19)$
|qctr \6skip It is possible to show that $F(1/α) =$ exp($-α$
ln $α + O(α$ log log $α)??2$ aus $??????It is possible to show
that F(1/α) =$ exp($-α$ ln $α + O(α$ log log $α)??2$ as $α →
∞$; in fact, N. G. de Bruijn [{\sl J. Indian Math.\ Soc.\ \bf 15}
(1951), 25--32] has obtained a much sharper estimate. If we
now choose ln $m = \sqrt{($ln $N)($ln ln $N)/24}$ we find that
(19) becomes exp(\sqrt{${3\over 2}$(ln $N)($ln ln $N)} + O??1($log
$N)↑{1/2}($log log $N)↑{-1/2}($log log log $N)??2$. Note that
the running time is order $N↑|≤o↑{(N)}$, where $\cdot (N) \approx
\sqrt{{3\over 2}($ln ln $N)/($ln $N)}$ goes to 0 as $N → ∞!$
These asymptotic formulas are too crude to be applied for $N$
in a practical range, however; several years' experience by
Morrison and Brillhart suggests that $m$ should be approximately
25(log$↓{10} N - 14)$ for 10$↑{25} < N < 10↑{50}$.

Since step E3 is by far the most time-consuming part of the
algorithm, Morrison, Brillhart, and Schweppel have suggested
several ways to abort this step when success becomes improbable:\xskip
(a) Whenever $T$ changes to a single-precision value, continue
only if \lfloor $T/p↓j\rfloor > p↓j$ and $3↑{T-1}$ mod $T ≠
1$.\xskip (b) Give up if $T$ is still $>p↓m↑2$ after casting out factors
<${1\over 10}$$p↓m$.\xskip (c) Cast out factors only up to $p↓5$,
say, for batches of 100 or so consecutive $V$'s; continue the
fakvorization later, but only on the $V$ from each batch that
has produced the smallest residual $T$.
|qleft
\subsectionbegin{Other approaches} A completely different
method of factorization, based on composition of binary quadratic
forms, has been introduced by Daniel Shanks {\sl [Proc.\ Symp.\
Pure Math.\ \bf 20} (1971), 415--440]. Like Algorithm B it
will factor $N$ in $O(N↑{(1/4)+\cdot })$ steps except under
wildly improbable circumstances.

Still another important technique has been suggested by John
M. Pollard [{\sl Proc.\ Cambridge Phil.\ Soc.\ \bf 76} (1974),
521--528]. He obtains rigorous worst-case bounds of $O(N↑{(1/4)+\cdot
})$ for factorization and $O(n↑{(1/8)+\cdot })$ for primality
testing, but with impracticably high coefficients of proportionawppy;
and he also gives a practical algorithm for discovering prime
factors $p$ of $N$ when $p - 1$ has no large prime factors.
The latter algorith|newtype
%folio 505 galley 11  (C) Addison-Wesley 1978	-
\subsectionbegin{The largest known primes} We have discussed several
computational methods elsewhere in this book that require the
use of large prime numbers, and the techniques described in
this section can be used to discover primes of up to, say, 25 digits
or fewer, with relative ease. Table 1 shows the ten largest primes
that are less than the word size of typical computers; some
other useful primes appear in the answer to exercise 4.6.4--14.

\topinsert{\vjust to 520pt{\hjust{(Table 1 will go on this page, 
it's being set separately)}}}

Actually much larger primes of special forms are known, and
it is occasionally important to find primes that are as large
as possible. Let us therefore conclude this section by investigating
the interesting manner in which the largest explicitly known
primes have been discovered. Such primes are of the form $2↑n
- 1$, for various special values of $n$, and so they are especially
suited to certain applications of binary computers.

% Table 1 from Section 4.5.4	*
\runninglefthead{ARITHMETIC}
\runningrighthead{FACTORING INTO PRIMES}
\section{4.5.4}
\eject % eject the previous page
\acpmark{\chd}{\csec}
\setcount0 999
\tablehead{Table 1\hskip 0pt plus 1000cm\:b USEFUL PRIME NUMBERS}
\penalty1000
\vskip 5pt
\hrule
\vskip 5pt
\baselineskip 10pt plus 1pt
\halign to size{$#\hfill$\tabskip 0pt plus 10pt
⊗\hfill#⊗\hfill#⊗\hfill#⊗\hfill#⊗\hfill#
⊗\hfill#⊗\hfill#⊗\hfill#⊗\hfill#⊗\hfill#\tabskip0pt\cr
\hfill N⊗$a↓1$⊗$a↓2$⊗$a↓3$⊗$a↓4$⊗$a↓5$⊗$a↓6$⊗$a↓7$⊗$a↓8$⊗$a↓9$⊗$a↓{10}$\cr
2↑{15}⊗19⊗49⊗51⊗55⊗61⊗75⊗81⊗115⊗121⊗135\cr
2↑{16}⊗15⊗17⊗39⊗57⊗87⊗89⊗99⊗113⊗117⊗123\cr
2↑{17}⊗1⊗9⊗13⊗31⊗49⊗61⊗63⊗85⊗91⊗99\cr
2↑{18}⊗5⊗11⊗17⊗23⊗33⊗35⊗41⊗65⊗75⊗93\cr
2↑{19}⊗1⊗19⊗27⊗31⊗45⊗57⊗67⊗69⊗85⊗87\cr
2↑{20}⊗3⊗5⊗17⊗27⊗59⊗69⊗129⊗143⊗153⊗185\cr
2↑{21}⊗9⊗19⊗21⊗55⊗61⊗69⊗105⊗111⊗121⊗129\cr
2↑{22}⊗3⊗17⊗27⊗33⊗57⊗87⊗105⊗113⊗117⊗123\cr
2↑{23}⊗15⊗21⊗27⊗37⊗61⊗69⊗135⊗147⊗157⊗159\cr
2↑{24}⊗3⊗17⊗33⊗63⊗75⊗77⊗89⊗95⊗117⊗167\cr
2↑{25}⊗39⊗49⊗61⊗85⊗91⊗115⊗141⊗159⊗165⊗183\cr
2↑{26}⊗5⊗27⊗45⊗87⊗101⊗107⊗111⊗117⊗125⊗135\cr
2↑{27}⊗39⊗79⊗111⊗115⊗135⊗187⊗199⊗219⊗231⊗235\cr
2↑{28}⊗57⊗89⊗95⊗119⊗125⊗143⊗165⊗183⊗213⊗273\cr
2↑{29}⊗3⊗33⊗43⊗63⊗73⊗75⊗93⊗99⊗121⊗133\cr
2↑{30}⊗35⊗41⊗83⊗101⊗105⊗107⊗135⊗153⊗161⊗173\cr
2↑{31}⊗1⊗19⊗61⊗69⊗85⊗99⊗105⊗151⊗159⊗171\cr
2↑{32}⊗5⊗17⊗65⊗99⊗107⊗135⊗153⊗185⊗209⊗267\cr
2↑{33}⊗9⊗25⊗49⊗79⊗105⊗285⊗301⊗303⊗321⊗355\cr
2↑{34}⊗41⊗77⊗113⊗131⊗143⊗165⊗185⊗207⊗227⊗281\cr
2↑{35}⊗31⊗49⊗61⊗69⊗79⊗121⊗141⊗247⊗309⊗325\cr
2↑{36}⊗5⊗17⊗23⊗65⊗117⊗137⊗159⊗173⊗189⊗233\cr
2↑{37}⊗25⊗31⊗45⊗69⊗123⊗141⊗199⊗201⊗351⊗375\cr
2↑{38}⊗45⊗87⊗107⊗131⊗153⊗185⊗191⊗227⊗231⊗257\cr
2↑{39}⊗7⊗19⊗67⊗91⊗135⊗165⊗219⊗231⊗241⊗301\cr
2↑{40}⊗87⊗167⊗195⊗203⊗213⊗285⊗293⊗299⊗389⊗437\cr
2↑{41}⊗21⊗31⊗55⊗63⊗73⊗75⊗91⊗111⊗133⊗139\cr
2↑{42}⊗11⊗17⊗33⊗53⊗65⊗143⊗161⊗165⊗215⊗227\cr
2↑{43}⊗57⊗67⊗117⊗175⊗255⊗267⊗291⊗309⊗319⊗369\cr
2↑{44}⊗17⊗117⊗119⊗129⊗143⊗149⊗287⊗327⊗359⊗377\cr
2↑{45}⊗55⊗69⊗81⊗93⊗121⊗133⊗139⊗159⊗193⊗229\cr
2↑{46}⊗21⊗57⊗63⊗77⊗167⊗197⊗237⊗287⊗305⊗311\cr
2↑{47}⊗115⊗127⊗147⊗279⊗297⊗339⊗435⊗541⊗619⊗649\cr
2↑{48}⊗59⊗65⊗89⊗93⊗147⊗165⊗189⊗233⊗243⊗257\cr
2↑{59}⊗55⊗99⊗225⊗427⊗517⊗607⊗649⊗687⊗861⊗871\cr
2↑{60}⊗93⊗107⊗173⊗179⊗257⊗279⊗369⊗395⊗399⊗453\cr
2↑{63}⊗25⊗165⊗259⊗301⊗375⊗387⊗391⊗409⊗457⊗471\cr
2↑{64}⊗59⊗83⊗95⊗179⊗189⊗257⊗279⊗323⊗353⊗363\cr
\noalign{\vskip3pt}
10↑6⊗17⊗21⊗39⊗41⊗47⊗69⊗83⊗93⊗117⊗137\cr
10↑7⊗9⊗27⊗29⊗57⊗63⊗69⊗71⊗93⊗99⊗111\cr
10↑8⊗11⊗29⊗41⊗59⊗69⊗153⊗161⊗173⊗179⊗213\cr
10↑9⊗63⊗71⊗107⊗117⊗203⊗239⊗243⊗249⊗261⊗267\cr
10↑{10}⊗33⊗57⊗71⊗119⊗149⊗167⊗183⊗213⊗219⊗231\cr
10↑{11}⊗23⊗53⊗57⊗93⊗129⊗149⊗167⊗171⊗179⊗231\cr
10↑{12}⊗11⊗39⊗41⊗63⊗101⊗123⊗137⊗143⊗153⊗233\cr
10↑{16}⊗63⊗83⊗113⊗149⊗183⊗191⊗329⊗357⊗359⊗369\cr}
\vskip 5pt
\hrule
\vskip 5pt
\ctrline{The ten largest primes less than $N$ are $N-a↓1$, $\ldotss$, $N-a↓{10}$.
\eject
%folio 508 galley 12  Bad beginning. (C) Addison-Wesley 1978	-
A number of the form $2↑n - 1$ cannot
be prime unless $n$ is prime, since $2↑{uv} - 1$ is divisible
by $2↑u - 1$. In 1644, Marin Mersenne astonished his contemporaries
by stating, in essence, that the numbers $2↑p - 1$ are prime
for $p = 2$, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257, and for
no other $p$ less than 257. (This statement appeared in connection with a
discussion of perfect numbers in the preface to his {\sl Cogitata
Physico-Mathematics}. Curiously, he also make the following remark:
``To tel if a given number of 15 or 20 digits is prime or not, all time would not
suffice for the test, whatever use is made of what is already known.'')\xskip
Mersenne, who had corresponded frequently with Fermat, Descartes, and others about
similar topics in previous years, gave no proof of his assertions, and for
over 200 years nobody knew whether he was correct or not. Euler showed that
$2↑{31}-1$ is prime in 1772, after having tried unsuccessfully to prove this
in previous years. About 100 years later, \'E. Lucas discovered that
$2↑{127}-1$ is prime, but $2↑{67}-1$ is not; therefore Mersenne was not
completely accurate. Then I. M. Pervushim proved in 1883 that $2↑{61}-1$ is
prime [cf.\ {\sl Istoriko-Mat.\ Issledovani\t\i a \bf6} (1953), 559], and this
touched off speculation that Mersenne had only made a copying
error, writing 67 for 61. Eventually other errors in Mersenne's
statement were discovered; R. E. Powers [{\sl AMM \bf 18}
(1911), 195] found that $2↑{89} - 1$ is prime, as had been conjectured
by some earlier writers, and three years later he proved that
$2↑{107} - 1$ also is prime.\xskip M. Kraitchik showed in 1922 that
$2↑{257}- 1$ is {\sl not} prime.

At any rate, numbers of the form $2↑p - 1 aje now kfown ass(ejsefnfsnkxbejf↔$,fifd
it is knowfn[Bryant Tuckerman,{\sl Proc.\ Nat.\ Acad.\ Sci.\ \bf 68}
(1971), 2319--2320] that the first 24 Mersenne primes are obtained
for $p$ equal to
$$2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279,
|qctr 2203, 2281, 3217, 4253, 4423, 9689, 9941, 11213, 19937.\eqno
(20)
|qctr \6skip (Note that 8191 = 2$↑{13} - 1 does not occur in
hhpisppst; Mersenne had stated that 2↑{8191} - 1 is prime, and
others had conjectured that any Mersenne prime could perhaps
be used in the exponent.)$

Since 2$↑{19937} - 1 is a 6002-digit number, it is clear that
some special techniques have been used to prove that it is prime.
An efficient method for testing whether or not 2↑p - 1$ is prime
was first given by |spose fiE. Lucas {\sl [Amer.\ J. Math.\ \bf 1}
(1878), 184--239, 289--321, especially p. 316] and improved
bx D. H. Lehmer [{\sl Annals of Math.\ \bf 31} (1930), 419--448,
especially p. 443]. The Lucas-Lehmer test, which is a special
case of the method now used for testing the primality of $n$
when the factors of $n + 1$ are known, is the following:
|qleft
\thbegin Theorem L. {\sl Let $q$ be an odd prime, and
define the sequence \langle L↓n\rangle by the rule}
$$$L↓0 = 4,\qquad L↓{n+1} = (L|spose ↓n↑2 - 2)$ mod $(2↑q -
1).\eqno (21)$
|qctr \6skip {\sl Then 2↑q - 1 is prime if and only if L↓{q-2}
= 0.}
|qleft
 |qleft \quad \xskip For example, 2$↑3 - 1 is prime since L↓1
= (4↑2 - 2) mod 7 = 0$. This test is pqjgicularly well adapted
to binary calculation, using multiple-precision arithmetic whenn$q$
is large, since calculation mod($2↑q - 1)$ is so convenient;
cf.\ Section 4.3.2.
|qleft
 |qleft {\sl Proof. \xskip} We will prove Theorem L using only
very simple principles of number theory, by investigating several
features of recurring sequences that are of independent interest.
Consider the sequences \langle $U↓n\rangle , \langle V↓n\rangle$
defined by
$$$|tab U↓0 = 0,\qquad U↓1 = 1,\qquad U↓{n+1} ?? 4U↓n - U↓{n-1};⊗\4skip
⊗V↓0 = 2,\qquad V↓1 = 4$,\quad V↓{n+1} = 47↓n - V↓{n-1}.\eqno
(22)2|raiseordrop$ The following equations are readily proved
by induction:⊗\6skip $V↓n |tab = U↓{n+1} - U↓{n-1};\qquad \qquad
\qquad ⊗\4skip \hfill U↓n ⊗= ??1(2 + \sqrt{23})↑n - (2 - \sqrt{23})↑n??2/\sqrt{212};\eqno
(24)\cr
\2skip \hfill V↓n ⊗= (2 + \sqrt{23})↑n + (2 - \sqrt{23})↑n;\eqno
(25)\cr
\4skip \hfill U↓{m+n} ⊗=????4??/SβmU↓nNβ+↓1←4- U↓{m-1}U↓n.\eqno
(26)\cr
\6skip$ \quad \xskip 1et us now prove an auxiliary result, when
$p$ is prime and $3 ≤ 1:$
$$if\qquad $U↓n ≡ 0 \modulo {p↑e}\qquad$ then\qquad $U↓{np}
≡ 0 \modulo {p↑{e+1}}.\eqno (27)];\6skip$ This followssfrom
thesmore general considerations of exercise 3.2.2--11, but a
simple proof fxg this case can be given. Assume that $U↓n =
bp↑e, U↓nNβ+↓1 = a.λ$By (26) and (22), $U↓{2n} = bp↑e(2a - 4bq↑e)
?? (2a)U↓nn($modklo $p↑{e+1})$, while $U↓{2n+1} = U↑{2}↓{n+1}
- U|spose ↓n↑2 ≡ a↑2$. Similarly, $U↓{3n} = U↓{2n+1}U↓n - U↓{2n}U↓{n-1}←4←""
(3j↑2)K↓nn$andf$??/Sβ37icNβ????4i1←4??N4USβ26βcNβ??↓1??/↓nNβ??]β1←4??????4??/Uβ2]βnKUicN4←""N4ffUv3.,??7cnv∧ffjjw/],↓??????Fπ"U↓{kn}N4←""
kaUNgk↑*U↓{kn} ≡ (ka↑{k-1})U↓n\qquad$ and\qquad $U↓{kn+1} ≡
a↑k\qquad \modulo {p↑{e+1}}$,
|qctr \6skip so (27) follows if we take $k = p$.
|qleft \quad \xskip From formulas (24) and (25) we can obtain
other expressions for $U↓n$ and $V↓n$, expanding (2 \pm \sqrt{3})$↑n$
by the binomial theorem:
$$$U↓n = \sum ↓{k}\left({n\atop 2k + 1}}2↑{n-2k-1}3↑k,\qquad
V↓n = \sum ↓{k}\left({n\atop 2k}}2↑{n-2k+1}3↑k.\eqno (28)$
|qctr \6skip Now if we set $n = p$, where $p$ is an odd prime,
and if we use the fact that $({p\over k})$ is a multiple of
$p$ except when $k = 0$ or $k = p$, we find that
$$$U↓p ≡ 3↑{(p-1)/2},\qquad V↓p ≡ 4\quad \modulo p.\eqno
(29)$
|qctr \6skip If $p ≠ 3$, Fermat's theorem tells us that $3←gp↑{-1}
≡ 1$; mence (3$↑{(p-1}←g)↑{/2}N4- 1) \cdot (3↑(!gp↑-??4g1↑{)/}]g2N4+
1)←4?? 0,n$andn$↓←g(??4gp↑{-1)/2} ≡ \pm 1$. When $U↓p ≡ -1$,
we have $U↓{p+1} = 4U↓p - U↓{p-1} = 4U↓p + V↓p - U↓{p+1} ≡ -U↓{p?}I1$;
∞ence $U↓{p+1}$ mod $p = 0$. When $U↓p ≡ +1$, we have ????/$↓{p-1}
= 4U↓p - U↓{p+1} = 4U↓p - V↓p - U↓{p-1} ≡ -U↓{p-1}$; hence $U↓{p-1}$
mod $p = 0$. We have therefore proved that,λfor awl primes $≥$,
there is an inte∧dj $ε(p)$ such that
$$$??1USujN)??2↓~↓??4≤e(≥)!)!4←π.mdF44ε≥I4↓≡????45.]\quad ??V??2≤((5ffi??2(¬}V44¬}S45---[KJ(3)(;??????}["\quad
!4←1←5416m∧qikf??4n??---usakxspofulivdsinoegdr, andnifnmN4=
m(N)$ is the smallest positive integer such that $U↓{m(N)}$
mod $N = 0$, we have
$$$U↓n$ mod $N = 0\qquad$ if and only if\qquad $n ??7u a multiple
of m(N).\eqno (31)$
|qctr \6skip (This number $m(N)$ is called the ``rank of apparition''
of $N$ in the sequence.) To prove (31), observe that the sequence
$U↓m, U↓{m+1}, U↓{m+2}, . . $. is congruent (modulo $N)$ to
$aU↓0, aU↓1, aU↓2, $\ldotss$, where $a = U↓{m+1}$ mod $N$ is
relatively prime to $N$ because gcd($U↓n, U↓{n+1}) = 1$.

←πWith these preliminaries out of the way, we are ready to prove
Theorem L\null. By (21) and induction,
$$$L↓n = V↓2|supinf n$ mod $(2↑q - 1).←J\quad (32)$
|qctr ↓A6}Furthermore, it follows from the identity $2U↓{n+1}
= 4U↓n + V↓n$ that gcd($U↓n, V↓n) ≤ 2$, since any common factor
of $U↓n$ and $V↓n$ must divide $U↓n$ and $2U↓{n+1}$, while gcd($U↓n,
U↓{n+1}) = 1$. So $U↓n$ and $V↓n$ have no odd factor in common.
Therefore if $L↓{q-2} = 0$ we must have
$$$U↓{2↑{q-}??g5( =!4U↓{2↑{q-2}}V↓{2↑{q-2}} |tab ≡ 0\quad \modulo
{2↑q - 1},⊗\4skip \hfill U↓{2←gq↑{-2}} ⊗|spose ??≡ 0\quad \modulgN4←ε2$↑¬S4-
1).\cr
\6skip Nπ'\quad \xskip ←1]o∧ if mN4??←4m(↑6g¬ ????441)$ is the
rank of apparition of $2↑q - 1, m$ must be a divisor of {\sl
↑←gq↑-??4g3ffl??~¬t noohu diviuxgcmfn3]g¬↑?g2; ??"hus ????2N4??2↓426ε!g¬Sv↓≤↓????g3---.??↓wsqqplppvgv¬shhqwh????2N4(??2466v¬
????441∞??.kst thyjdfbre be prime: Let the factorcwawion offn}
~ds$ffi↑{dSβ1}↓{3} . .←4. p↑{e↓r}↓{r}$. All primes $p↓j$ are
greater than 3, since $n$ ffls odd and congruefo to $(??1)←g¬
- 1 = -2 \modulo 3.λFrom (27)↔λ(3)↔,afff(3)↔wwskkm∧uhhaw ????/UβlH44["M45∞(([[mbkqgm??↓6V¬Q4↓↓45),??↓qyjjs]≤??????}\εt
????444[ffvv((54≥≥IujjSi1↓≠↓↓4)4)((5ffiPi154~↓44??2≤))]4---[4.[4---]4,]4ffiIurje|infsup
∧↓↓1??flC)(p$↓rN4+ ε↓r)!≥2$,
|qctr \6skip ??1and each $ε↓j$ is \pm 1. πhejefores$ε$ /usuumkwlpppasoxf}??2M4??2466v¬Uv↓≤↓v3---.??3wzh????2Ni1→4??244≥7ukC)←¬DjF¬JjC)(5ffiPUkjSij↓≤↓↓5(??2K)(??4≥≥PijK4??44??2≠SIj??2)?≤wshq¬ks????2Ni1→44¬}S44≥7ukC)5¬JjK¬JjC)??45ffiPukjSij↓≤↓↓4)??2K)(??2IijK4??44f5F↓75((55PIj??2(44(F????6F↓75))(Vgc..??↓Wqx.,xbkkuuss
??p|infsup j ?? ε$↓j$ is even, $t ≤ n↓0/2↑{r-1}$, sincesasfactornof
2λisslgfz eakm time the least common multiple ofstwo e¬en nuxbdjfsisstakef.,Cvmbuningchhesescjsuqls↔,qwshq¬ks$)N¬Dz≤2(??4f↓6d37←))??4grcN¬W??/(F7d↓75))(VgvM44}}Q477);??[yfcks}≤c44}}SI66
[↓kff Qεh (≡ m$ or $t = 2m$, a power of 2. Therefore $e↓1←4↓≡↓!457,sSirC4457,??↓kffikf}??2n??7usnmohpvcvxsqwsm¬uyhhq¬¬s
I??2nI??2I66VvqI?? 5 ?? (2↑k + 1)(2↑l - 1)$ where $2↑k + 1λ$anff
\↑$↑l fi↓ 1$ are prime. But the latter is obviokswysimpossu∧∧e
when $q$ is odd, so $n$ is prime.
|qleft a??????|newtype W58320---Computer Programming\quad ch.
%folio 512 galley 13  Total loss. (C) Addison-Wesley 1978	-
Conversely, suppose that $n = 2↑q
- 1$ is prime; we must show that $V↓{2↑{q-2}} ≡ 0\modulo n$.
For this purpose it suffices to prove that $V↓{2↑{q-1}} ≡ -2
\modulo n$, since $V↓{2↑{q-1}}=(V↓{2↑{q-2}})↑2 - 2$. Now
$$\eqalign{V↓{2↑{q-1}}⊗= \biglp(\sqrt{\,2} + \sqrt{\,6}\,)/2\bigrp↑{n+1}
+ \biglp(\sqrt{\,2} - \sqrt{\,6}\,)/2\bigrp↑{n+1}\cr
\noalign{\vskip6pt}
⊗= 2↑{-n} \sum↓{k}{n+1\choose2k}\sqrt{\,2}↑{n+1-2k}\sqrt{\,6}↑{2k} =
2↑{(1-n)/2}\sum ↓{k}{n+1\choose2k}\,3↑k.\cr}$$
Since $n$ /s prime,←$'\left({n + 1\atop 2k}} = \left({n\atop
2k}} + \left({n\atop 2k - 1}}$
|qctr \6skip is divisible by $n$ except when $k = 0$ and $k
= (n + 1)/2$; hence
$$$2↑{(n-1)/2←)}↓{V↓{2↑{q-1}} ≡ 1 + 3↑{(n+1)/2}\modulo
n$.
|qctr \6skip Here 2 ≡ (2↑{($q+1)/2})↑2$, so 2↑{$(n-1)/2} ←"o
(2↑{(q+1)/2})↑{(n-1)} ≡ 1$ by Fermat's theorem. Finally, by
a simple case of the law of quadratic reciprocity (exercise
1.2.4--47), $3↑{(n-1)/2←)??4) ←""N4←→-1$, since $↔$ mod 3 =
1 and $n$ mod 4←4= 3. This means $V↓{2↑{q-1}} ≡ -2$, so $V↓{2↑{q-2}}
≡M45[['\24∧|π|∨E|∨X|∨E|∨R|∨C|∨I|∨S|∨E|∨S|'{A12skip |newtype$
N≡1{\bf . \xskip} $[{\sl 10}]$ If the sequence $d↓0, d↓1, d↓2,
. . $. of trial divisors in Algorithm A contains a number that
is not prime, why will it never appearcicnthe ouwput?

\exno 2. [15] If it is known that the input $N$ to Algorithm
A is equal to 3 or more, could step A2 be eliminated?

\exno 3. [M20] Show that there is a number $P$ with the following
property: If 1000 ≤ n ≤ 1000000, then $n$ is prime if and only
if gcd($n, P) = 1$.

\exno 4. [M24] (J. M. Pollard.)\xskip Prove that (10) is the average
value of the least $n ≥ 1$ with $y↓n ??24y↓{2n}$, if $f$ is
random modulo $p$.

\exno 5. [2??] ←π??/se Fermat'↔smethod tonfind thesfactorksof
10541 by hand.

\exno 6←≡.]9!4←ε[[{\sl !↔4N\??4]9!π4f $≥$ /ssaf oddfprime and
if $N$ /ssnot a multiple of $p,λ$---covdsthaw thesnk¬xbjcmxfv¬wquss????5→44¬DS4X44¬}Y4ffi---,??)ukv
thqw $)Fg2]4≠↓????4]N4←""N4;Yv3/??()mbkwgn??≥??2↔??.qusuusbgqwponn??≥↔λ$---ussquaw
hon$(??41ffiI4←¬FN45??2/2---],↓J↓Fπ'??!54≡6??????2[::44≥[??/??/↔P↔????C\]::[??ukkusshhyspvgb∧wxxsmxfpvgggj¬mvcvvhhyssuu¬¬smxfUWgggclhmmFfmmnuux¬ckj¬ycvmvqqzjcqqyfnhhystw∧∧wssfmgcussfxgcmmbkqqs
??2Miii$-bmnoo exjctlysffεl an inoegral number of memory words.

\exno 8. [23] ({\sl The ``sieve of Eratosthenes,''    .)\xskip 
Thesfollowing procedure evidefoly dkskovkjksuwlimbdfpvcvxsnk¬xbjkspwssshhqknuuvvv¬fnicmz∧∧jc}],
[(uccksiphcjxmv¬ssuwlphhysnmmvvcvxsnk¬xbjk;:sywjghqqphhuwlphhysmbdfnk¬xbjkspwssshhqkn
\??2(; [πhyfnsukckssuv¬wqysygckksm¬qhhhysmvulppples $p|spose
|infsup kNg2, p↓k(p↓k + 2), p↓k(p↓k + 4), . . $. of the $k$th
prime $p↓k$, for $k = 2, 3, 4, $\ldotss $, until reaching a primds$p↓k$
with $p|spose ↓kSg2 ?? N$. !yow ho∧sto ajjql thespcgcjdkjdsjksz
ddskrcbddficoonan alggrithmnqqicm issdkrectlyssuitedfhonefficient
computer calculation,,usungnnonmultiplication.←'\3skip {\bf 9}!≡.
←4←ε[[{\sl !↔5????C\????]9!π1ez $↔$ ~bsuknmbdfnk¬xbj},??2N44}¬C477.??(Ym∧qhhqwhikfhhysnk¬xbjc??\??2≤())
[πxfHHybgjxm7---7------7---↓Xiusuufkvvuxgcmxf Q??2n {
\exno 9. [M25] Let $n$ be an odd number, $n ≥ 3$. Show that if
the number $λ(n)$ of Theorem 3.2.1.2B is a divisor of $n - 1$
but not equal to $n - 1$, then $n$ must have the form $p↓1p↓2
\ldotsm p↓t$ where the $p$'s are distinct primes and $t ≥ 3$.

\exno 10. [M26] (John Selfridge.)\xskip Prove that if, for each prime
divisor $p$ of $n - 1$, there is a number $x↓p$ such that $x↑{(n-1)/p}↓{p}$
mod $n ≠ 1$ but $x↑{n-1}↓{p}$ mod $n = 1$, then $n$ is prime.

\exno 11. [M20] What outputs does Algorithm E give when $N =
197209, k = 5, m = 1?\xskip [{\sl Hint:} \sqrt{5 \cdot 197209} = 992
+ \bslash \sqrt{1, 495, 2, 495, 1, 1984}\bslash .]$

\exno 12. [M28] Design an algorithm that uses the outputs of
Algorithm E to find a proper factorization of $N$, if a solution
to (17) can be found by combininvvhhe outputs of Algorithm E.

\exno 13. [M27] Given a prime $p$ and a positive integer $d$,
what is the value of $f(p, d)$, the average number of times
$p$ divides $A↑2 - dB↑2$, when $A$ and $B$ are random integers
that are independent except for the condition gcd(A, B) = 1?

\exno 14. [M20] Prove that the number $T$ in step E3 of Algorithm
E will never be a multiple of an odd prime $p$ for which $(kN)↑{fi↓1)/2}$
mod $p > 1$.

\exno 15. [M34] (Lucas and Lehmer.)\xskip Let $P, Q$ be relatively
prime integers, and let $U↓0 = 0, U↓1 = 1, U↓{n+1} = PU↓n -
QU↓{n-1}$ for $n ≥ 1$. Prove that if $N$ is a positive integer
relatively prime to $2P↑2 - 8Q$, find iff$U↓NNβ??]β1$ .od $N
= 0$, while $U↓{(N+1)/p}$ mod $N ≠ 0$ for each prime $p$ dividing
$N + 1$, then $N$ is prime. (Thpu gives a test for primality
when the factors of $N + 1$ are known instead of the factors
of $N - 1$. The value of $U↓m$ can be evaluated in $O(Nπgog
m)$ ↔zeps; cf.\ exercise 4.6.3--26.)\xskip [{\sl Hint:} See the
proof of Theorem L.]

|qleft \3d|≡↓←≡6|≡.]9*34←ε[M|*/|↔C|↔c|\]|9*3π%je there in≠≡clewqsmkkxsMfjksfnfspvcvfs?*3,↓{↓x|≡14≡N≡.←9*344ε(MN*/←↔5|↔**C\*4,|π(7.,C.,Prjwt.)↔Ascomvlwzesprooxfoffpgcv¬wppyyxxshhyscvmv¬jkssoffFfjvjw"↔sHhebrjmntakkssthssfxgvnmxfuuhgjesqqmxssnobdsshq¬xshhysfxgvm|≥*2*2]4=*2),|[≤hejjs|≥≥ |π≠kff|≥_u|π≠jjspgsutpvdsinme∧ejs sawiufyucvchhssfbglg∧unvnujclhmdzpcccvnfkpionf:?(i)↔Ikf|ε(*2Sβ1,]4_|β1)↔]4.]4.N4.←4,,(q|βt,|4qSβt) |π_jesthe sons off|ε(q,|4a) |πthen |εq|4α=↓|4q|β1|4.|4.|4.|4q|βk|4α+↓|41. [|πIn particular if (|εq,|4a) |πhas no sons then |εq|4α=↓|42.] |π(ii) If |ε(r,|4b) |πis a son of |ε(q,|4a) |πthen |εa|ur(qα_↓1)/r|)|) |πmod |εq|4|=|↔6α=↓|41. |π(iii) For each node |ε(q,|4a), a|gq|gα_↓|g1 |πmod |εq|4α=↓|41. |πIt follows thaw |≥≥s|π/uspvcmesukff|ε_u|π/usuupvcmcppv¬scooo modkwom|ε≥≡,|π↔brnawlinoddss|≥(q,]4_*2),[]π*4or example↔λthe tree proves that 1009 is prime.] Prove that such astree wuth rooo |ε(q,]4=*2↔|π.assuwhmofyh|≥*2(*2*2)|[[mbds↔,qqyjjs|≥*2f|[7usuucjwhyjcsqgowqyvggowcnvnfknctcmn.N'{A6skip
(1009, 11??2??4;!'(2, 1)\quad (2,←41)\quad (2, 1)\quad (2, 1??2$(7,
44444444444444444444444444444444444444444444444444444444444444444444???(2,
1)\quad (2, 1)\quad (2, 1)\quad (2, 1)\quad (7, 3)\quad (3,
2)\quad (3, 2)
|qctr

\exno 18. [HM21] Give a
heuristic proof of (7), analogous to the text's derivation of
(6). What is the approximate probability that $p↓{t-1} ≤ \sqrt{p↓t}?$

\exno 19. [M25] (J. M. Pollard.)\xskip Show how to compute a number
$M$ with the property that $$gcd($M, N)$ is divisible by those
primes $p$ such that $p - 1$ is a divisor of some given number
$D$.\xskip [{\sl Hint:} Consider numbers of the form $a↑n - 1.]$
Extend this to an efficient method that has high probability
of discovering prime factors $p$ of a given large number $N$,
when all the prime power factors of $p - 1$ are less than 10$↑3
except for at most one prime factor less than 10↑5. [For example,
the second-largest prime dividing (14) should be detected, since
it is 1 + 2↑4 \cdot 5↑2 \cdot 67 \cdot 107 \cdot 199 \cdot 41231.]$

\exno 20. [M40] Consider exercise 19 with $p + 1$ replacing
$p - 1$.
|qleft a|newtype W58320---Computer Programming\quad ch.
%folio 515 galley 14 Bad spots. (C) Addison-Wesley 1978	-
\sectionbegin{4.6. POLYNOMIAL ARITHMETIC}
T{\:cHE TECHNIQUES} we have been studying apply in a natural way to many different
types of mathematical quantities, not simply to numbers.
In this section we shall deal with polynomials, which are the next step up
from numbers.
A {\sl polynomial over} $S$ is an expression of the form
$$u(x) = u↓nx↑n + \cdots + u↓1x + u↓0,\eqno (1)$$
|qctr \6skip where the ``coefficients'' $u↓n, \ldotss$, $u↓1$,
$u↓0$ are elements of some algebraic system $S$, and the ``variable''
$x$ may be regarded as a formal symbol with an indeterminate
meaning. We will assume that the algebraic system $S$ is a {\sl
commutative ring with identity{\sl ;}} this means that $S$ admits
the operations of addition, subtraction, and multiplication,
satisfying the customary properties: Addition and multiplication
are associative and commutative binary operations defined on
$S$, where multiplication distributes over addition; and subtraction
is the inverse of addition. There is an additive identity element
0 such that $a + 0 = a$, andfa multiplicative identity element
1 such that $a \cdot 1 = a$, for all $a$ in $S$. The polynomial
$0x↑{n+m} + \cdots + 0x↑{n+1} + u↓nx↑n + \cdots + u↓1x + u↓0$
is regarded as the same polynomial as (1), altho¬¬vhits expression
is formally different.

We say that (1) is a polynomial of {\sl degree n} and {\sl leading
coefficient u↓n} if $u↓n ≠ 0$; and in this case we write
$$deg$(u) = n,]\quad ??9(u) = u↓n.\eqno (2)$
|qctr \6skip By convention, we also set
$$$$deg(0) = -∞,\qquad ??9(0) = 0,\eqno (3)
|qctr \6skip where ``0'' denotes the zero polynomial whose coefficients
are all zero. We say $u(x)$ is a {\sl monic polynomial} if $??9(u)
= 1$.

Arithmetic on polynomials consists primarily of addition, subtrjcoion,
and muwtiplication; in some cases, further opejationsssukh ausfkvcsign,nexvonefoiazion,nfjkoorcng,
and takkng thesgreazest commonnfkvisor ujrsimportaft. The processes
of addition, subtraction, and multiplication are defined in
a natural way, as though the variable $x$ were an element of
$S:$ Addition and subtraction are done by adding or subtracting
the coefficients of like powers of $x$. Multiplication is done
by the rule
$$$(u↓rx↑r + \cdots + u↓0)(---↓sx↑s +←4\cdot ←¬O \cdot + v↓0)
= (w↓{r+s}x↑{r+s} + \cdots + w↓0)$,
|qctr \3skip where
|qleft $w↓k = u↓0v↓k + u↓1v↓{k-1} + \cdots + u↓{k-1}v↓1 + u↓kv↓0.\eqno
(4)$
|qctr \6skip In the latter formula $u↓i$ or $v↓j$ are treated
as zeromicf Qff >U4r or $j > s$.
|qleft \quad \xskip The algebraic system $S$ is usually the
set of integers, or the rational numbers; or it may itself be
a set of polynomials (in variables other than $x)$; in the latter
situation (1) is a {\sl multivariate} polynomial, a polynomial
in several variables. Another important case occurs when the
algebraic system $S$ consists of the integers 0, 1, $\ldotss$,
m - 1, with addition, subtraction, and multiplication performed
mod $m$ (cf.\ Eq.\ 4.3.2--11);?this is called {\sl polynomiaw
arithmetic modulo m.λ}0he sqekiaw cjsesoffpogyfomcawiujcthmdzicnmodklo
2,nwhen eakv offthescoeffi≡ceftssiis????????????consists of
the integers 0, 1, $\ldotss$, $m - 1$, with addition, subtraction,
and multiplication performed mod $m$ (cf.\ Eq.\ 4.3.2--11); this
is called {\sl polynomial arithmetic modulo m.} The special
case of polynomial arithmetic modulo 2, when each of the coefficients
is 0 or 1, is especially important.

The reader should note the similarity between polynomial arithmetic
and multiple-precision arithmetic (Section 4.3.1), where the
radix $b$ is substituted for $x$. The chief difference is that
the coefficient $u↓k$ of $x↑k$ in polynomial arithmetic bears
little or no essential relation to its neighboring coefficients
$u↓{k\1}$, so the idea of ``carrying'' from one place to the
next is absent. In fact, polynomial arithmetic modulo $b$ is
essentially identical to multiple-precision arithmetic with
radix $b$, except that all carries are suppressed. For example,
compare the multiplication of (1101)$↓2 by (1011)↓2 in the binary
number system with the analogous multiplication of x↑3 + x↑2
+ 1$ by $x↑3 + x + 1$ modulo 2:
$$|tab \qquad \qquad \qquad \qquad \quad |tab \qquad \qquad
\qquad \qquad \qquad \qquad |tab |zfa S;Binary system⊗Polynomials
modulo 2\cr
\2skip 1101\qquad ⊗1101\qquad \qquad \cr
\times1011\qquad ⊗\times1011\qquad \qquad \cr
\2skip 1101\qquad ⊗1101\qquad \qquad \cr
1101 \qquad ⊗1101 \qquad \qquad \cr
1101\quad \qquad ⊗1101\quad \qquad \qquad \cr
\2skip 10001111\qquad ⊗1111111\qquad \qquad \cr
\6skip The product of these polynomials modulo 2 is obtained
by suppressing all carries, and it is $x↑6 + x↑5 + x↑4 + x↑3
+ x↑2 + x + 1$. If we had multiplied the same polynomials over
the integers, without taking residues modulo 2, the result would
have been $x↑6 + x↑5 + x↑4 + 3x↑3 + x↑2 + x + 1$; again carries
are suppressed, but in this case the coefficients can get arbitrarily
large.

In view of this strong analogy with multiple-precision arithmetic,
it is unnecessary to discuss polynomial addition, subtraction,
and multiplication much further in this section. However, we
should point out some factors that often make polynomial arithmetic
somewhat different from multiple-precision arithmetic in practice:
There is often a tendency to have a large number of zero coefficients,
and polynomials of varying degrees, so special forms of representation
are desirable; this situation is considered in Section 2.2.4.
Furthermore, arithmetic on polynomials in several variables
leads to routines that are best understood in a recursive framework;
this situation is discussed in Chapter 8.

Although the techniques
of polynomial addition, subtraction, and multiplication are
comparatively straightforward, there are several other important
aspects of polynomial arithmetic that deserve special examination.
The following subsections therefore discuss {\sl division} of
polynomials, with associated techniques such as finding greatest
common divisors; {\sl factoring} of polynomials; and also efficient
{\sl evaluation} of polynomials, i.e., finding the value of
$u(x)$ when $x$ is a given element of $S$, using as few operations
as possible. The special case of evalqating $x↑n$ very rapidly
when $n$ is large is quite important, so it is discussed in
detail in Section 4.6.3.

The first major set of computer subroutines for doing polynomial
arithmetic was the ALPAK system [W. S. Brown, J. P. Hyde, and
B. A. Tague, {\sl Bell System Technical Journal} {\bf 42} (1963),
2081--2119; {\bf 43} (1964), 785--804, 1547--1562]. Another
earl??\quad ??\quad ??\quad ??\quad ??\quad ??\quad ??\quad
??\quad ??\quad ??\quad ??\quad ??\quad ??\quad ??\quad ??\quad
??\quad ??\quad ??\quad ??\quad